백준 1920번(수 찾기)

in Algorithm


문제 풀이

🔖 소스 코드

이번 문제는 이분탐색 알고리즘을 사용해서 푸는 간단한 문제였다.


정렬되어 있는 배열에서 데이터를 찾으려 시도할 때, 순차탐색처럼 처음부터 끝까지

하나씩 모든 데이터를 체크하여 값을 찾는 것이 아니라, 탐색 범위를 절반씩 줄여가며

찾아가는 방법이다.


시간복잡도

탐색 대상값을 찾을 때, 이분탐색은 탐색 대상을 절반씩 줄여나가면서 탐색을 한다.

따라서 시간 복잡도는 어떤 경우에도 O(logN) 을 갖는다.


Arrays.binarySearch0

자바의 Arrays 클래스는 해당 메서드를 제공해주는데 아래와 같다.

private static int binarySearch0(long[] a, int fromIndex, int toIndex, long key) {
    int low = fromIndex;
    int high = toIndex - 1;

    while (low <= high) {
        int mid = (low + high) >>> 1;
        long midVal = a[mid];

        if (midVal < key)
            low = mid + 1;
        else if (midVal > key)
            high = mid - 1;
        else
            return mid; // key found
    }
    return -(low + 1);  // key not found.
}