Binary Search

이진 탐색(binary search)은 정렬된 데이터 집합을 이분화하면서 탐색하는 방법이다. 예를들어 비유하면, 가나다순으로 정렬되어 있는 전화번호부에서 임의의 사람에 대한 전화번호를 찾는 경우다.

 

 

① 중간에 위치한 데이터인 11과 찾고자 하는 15가 같은지 비교한다.

② 중간에 위치한 데이터인 11보다 찾고자 하는 데이터인 15가 크므로 중간 데이터 11의 오른쪽에 위치한 데이터들에 대해 이진 탐색을 수행한다.

③ 탐색 영역의 중간에 위치한 데이터인 17과 찾고자 하는 15가 같은지 비교한다.

④ 중간에 위치한 데이터인 17보다 찾고자 하는 데이터인 15가 작으므로 중간 데이터 17 왼쪽에 위치한 데이터들에 대해 이진 탐색을 수행한다.

⑤ 탐색 영역의 중간에 위치한 데이터인 15와 찾고자 하는 15가 같은지 비교한다. 원하는 데이터이므로 탐색을 종료한다.

 

Java Code

public class Binary {
    static int binarySearch(int pick) {
        int[] arr = { 1, 3, 8, 11, 15, 17, 20 };
        int low = 0;
        int high = arr.length;
        int mid;

        while (low <= high) {
            mid = (low + high) / 2;

            if (pick == arr[mid]) {
                return mid;
            } else if (pick < arr[mid]) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }

        return -1; // 탐색 실패
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int input = sc.nextInt();
        System.out.println(binarySearch(input) + "번 인덱스 값입니다.");
        sc.close();
    }
}

이진 탐색의 시간 복잡도는 O(log n)이다.
단, 정렬된 데이터를 탐색해야 한다.