이분 탐색(Binary Search)

이분 탐색(Binary Search)

- 정렬되어 있는 배열에서 데이터를 찾으려 할 때 탐색 범위를 절반으로 줄여가며 데이터를 찾는 방법 

- 배열의 중앙값을 조사하여 탐색하고자 하는 값이 왼쪽 혹은 오른쪽에 있는지 알아내어 검색해야할 배열의 크기를 반으로 줄인다. 

- 순차 탐색에 비해 굉장히 효율적인 알고리즘 

 ex) 10억명의 이름이 담긴 배열에서 특정 이름을 찾으려면 순차탐색에서는 약 5억번의 비교가 필요하지만 이분탐색으로는 약 30번의 비교만으로 찾을 수 있다. 

 

* 이분 탐색을 할 수 있는 데이터의 조건 : 정렬이 된 배열이어야 함. 

* 이분 탐색에 적합한 데이터 : 삽입, 삭제가 빈번하기보다는 고정된 데이터 

 

이분 탐색 동작 과정 

ex1) 배열 [1,3,5,6,7,9,11,20,30]에서 5을 검색  ① 7(중앙값) 과 비교 - 5 < 7 이므로 앞부분만 다시 탐색 ② 3(중앙값) 과 비교 - 5 > 3 이므로 뒷부분만 다시 탐색   ③ 5(중앙값) 과 비교 - 5 == 5 이므로 탐색 성공

ex2) 배열 [1,3,5,6,7,9,11,20,30]에서 2를 검색  ① 7(중앙값)과 비교  - 2 < 7 이므로 앞부분만 다시 탐색 ② 3(중앙값)과 비교 - 2 < 3 이므로 앞부분만 다시 탐색  ③ 1(중앙값)과 비교 - 2 > 1이므로 뒷부분만 다시 탐색  ④ 더 이상 남은 항목이 없으므로 탐색 실패

 

JAVA code

package com.algorithm.binarysearch;

/**
 * 이분 탐색
 */
public class binarySearch {

    public static void main(String[] args) {

        int[] array = {1, 3, 5, 6, 7, 9, 11, 20, 30};
        int a = 30;

        System.out.println(searchBinary(array, a));
    }

    public static int searchBinary(int[] array, int a) {
        int first = 0;
        int last = array.length - 1;

        while (first <= last) {
            int mid = (first + last) / 2;

            if (array[mid] == a) {
                return mid;
            }

            if (a > array[mid]) {
                // 뒷부분만 다시 탐색
                first = mid + 1;
            } else {
                // 앞부분만 다시 탐색
                last = mid - 1;
            }
        }
        return -1;

    }
}