이분 탐색(Binary Search)

개념

• 구간 내 절반을 잘라가면서 값을 찾아나가는 탐색 방법

시간복잡도

• O(log N)

전제 조건

• 탐색하는 범위가 정렬되어 있어야 한다

메커니즘

1. 탐색 범위내의 배열의 중간인덱스를 구한다.
2. 중간 인덱스의 값과 key값을 비교한다.
3. 값이 중간 값보다 작다면 왼쪽 부분을, 값이 중간 보다 크다면 오른쪽 부분을 탐색하고, 같다면 해당 인덱스를 반환한다.

세부적인 탐색 방법

1. 정확한 key 값 찾기
2. 상한 값 찾기
3. 하한 값 찾기

정확한 key 값 찾기

이름 그대로 key 값과 정확하게 일치하는 값을 찾는 경우이다.

예를 들면, [1, 2, 3, 4, 5] 중에서 3을 찾는 경우 이 방식을 사용한다.

코드로 구현하면 다음과 같다.

static int binarySearch(int[] arr, int key) {
    int left = 0;
    int right = arr.length - 1;
    
    while (left <= right) {
        int mid = (left + right) / 2;
        
        if (key < arr[mid]) {
            right = mid - 1;
        } else if (key > arr[mid]) {
            left = mid + 1;
        } else {
            return mid;
        }
    }
    
    return -1;
}

상한 값 찾기

탐색 범위에서 key값이 가능한 최대 범위를 탐색할 때 사용한다.

예를 들면 나무의 길이가 [802, 743, 457, 539] 이렇게 주어졌고, 같은 크기로 잘라서 11개의 나무를 얻고자 할 때 자를 수 있는 최대 길이를 구하라.

이러한 경우에는 이분 탐색에서 상한 값을 찾아내면 된다.

코드로 구현하면 다음과 같다.

static int upperBound(int[] arr, int key) {
    int low = 0;
    int high = arr.length - 1;
    
    while (low < high) {
        int mid = (low + high) / 2;
        
        if (key < arr[mid]) {
            high = mid;
        } else {
            low = mid + 1;
        }
    }
    
    return low;
}

하한 값 찾기

상한 값 찾기와 반대로 가능한 최소 범위를 탐색할 때 사용한다.

코드로 구현하면 다음과 같다.

static int upperBound(int[] arr, int key) {
    int low = 0;
    int high = arr.length - 1;
    
    while (low < high) {
        int mid = (low + high) / 2;
        
        if (key <= arr[mid]) {
            high = mid;
        } else {
            low = mid + 1;
        }
    }
    
    return low;
}

정리하는데 도움을 받은 자료들

이분 탐색 개념

[백준] 1920번 : 수 찾기 - JAVA [자바]

상한, 하한 개념

[백준] 10816번 : 숫자 카드 2 - JAVA [자바]