이진 탐색

Binary Search

리스트의 탐색 범위를 반씩 줄여나가면서 타겟의 위치를 찾는 알고리즘. 탐색 시 O(log n) 성능을 보인다. 리스트가 먼저 정렬되어 있어야만 binary seach 알고리즘을 적용할 수 있으며 분할 정복 기법을 사용한다.

 

리스트에서 타겟의 인덱스를 빠르게 찾거나 해가 존재할 범위에서 해를 빠르게 찾는데 사용된다.

Java의 binary search

자바의 Arrays, Collections 클래스는 binarySearch 정적 메서드를 제공한다.

Arrays.binarySearch 정적 메서드

binarySearch 메서드의 리턴 값은 아래와 같다.

• 리스트에서 키를 찾았으면 키 인덱스 리턴
• 리스트에서 키를 찾지못하면 키가 삽입되어야할 인덱스 값인 insertion point 값을 구한 뒤 -(insertion point + 1) 리턴

binarySearch 메서드의 코드이다.

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

        while (low <= high) {
            int mid = (low + high) >>> 1;
            int 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.
    }

Lower bound, Upper bound

binarySearch를 변형하여 lower bound, upper bound 방식으로 동작 시킬 수도 있다.

• lower bound : 리스트에서 키 값 이상이 처음 나타나는 위치를 반환
• upper bound : 리스트에서 키 값을 초과하는 값이 처음 나타나는 위치를 반환

Lower bound 방식 코드

static int binary_search(int[] a, int fromIndex, int toIndex, int key) {
        int low = fromIndex;
        int high = toIndex - 1;
        int lower_bound = toIndex;

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

            if (midVal < key) {
                low = mid + 1;
            }
            else {
                high = mid - 1;
                lower_bound = mid;
            }
        }
        return lower_bound;
    }

Upper bound 방식 코드

static int binary_search(int[] a, int fromIndex, int toIndex, int key) {
        int low = fromIndex;
        int high = toIndex - 1;
        int upper_bound = toIndex;

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

            if (midVal <= key) {
                low = mid + 1;
            }
            else {
                high = mid - 1;
                upper_bound = mid;
            }
        }
        return upper_bound;
    }