이분탐색 실수없이 짜기

2023-01-16

[0, 1, 4, 8, 9]와 같은 정렬된 구조에서 특정 값의 위치를 찾는 문제를 풀어봅시다.

array[i]와 같이 접근하는 연산 subscript 연산의 비용이 C라고 하고, 배열의 길이가 N이라고 합시다

나이브하게 보면, 앞부터 순서대로 찾으면 총 CN의 비용이 발생합니다. 이를 순차 탐색이라고도 표현합니다.

다음 아이디어를 더해봅시다.

우리가 만약 1을 본다면, 정렬되어있음을 알고 있기 떄문에 찾고자하는 값 4보다 작은 값들만 있을 왼쪽을 보지 않아도 됩니다.
즉, 비용의 기댓값은 $problem(N, C) = (problem(N - k) + C) * success + (problem(k) + C) * fail$ 의 비용이 발생하고, $success = fail = 0.5$ 입니다. ($k = $처음 고른 숫자의 위치)
k가 1, 2 등의 상수인 경우, 순차 탐색과 별반 다를게 없으니 반으로 나눠보기로 합시다. $problem(N, C) = problem(N/2, C) + C$

이렇게 반으로 계속 나눠가며 찾는 경우, $Clog2(N)$, $O(logN)$ 만큼의 비용이 발생함을 알 수 있습니다.

다만 이를 잘못 구현하게 되면..

영원히 종료되지 않습니다.
한칸 앞이나 뒤의 값을 반환합니다
상한을 반환해야하는지 하한을 반환해야하는지 혼동합니다.

등 여러 오류가 발생할 수 있으며, 특정 값이 아닌 좀 더 복잡한 조건을 요구하는 경우 혼동할 수 있습니다.

code

처음으로 돌아가서, [0, 1, 4, 8, 9]에서 값을 찾는다고 하죠.

만약 모든 원소에 값이 4면 true, 아니면 false로 바꾸면 어떻게 될까요?

[0:false, 1:false, 4:true, 8:false, 9:false]

이분 탐색을 사용할 수 있던 조건인 ‘정렬됨’이 사라지게 됩니다. 따라서 정렬됨을 유지하기 위해 4 이상인 경우 true, 아니면 false로 바꿔봅시다.

[0:false, 1:false, 4:true, 8:true, 9:true]

4 이상인 값이 존재하지 않으면 어떻게 해야할까요?

[0: false, 1:false, 3:false, 3:false]

마지막 위치인 3의 위치를 반환하면 3의 위치에 실제로 4 이상인 값이 있다고 생각할 수 있으니 가상의 값을 추가해 N+1번째(0-based-index = N)를 반환하도록 약속합시다.

[0: false, 1:false, 3:false, 3:false, infinity: true]

우리는 [begin=0, end=N+1] 위치의 원소 속 true인 가장 작은 위치를 찾고자 합니다. 이렇게 begin과 end를 정의하면 다음과 같은 성질을 가집니다.

end위치는 true입니다.
[begin, end]는 처음 true가 나타나는 위치를 포함합니다.

이 성질을 유지하는 채로 문제를 변환($problem(N, C) -> problem(N/2, C) + C$)해야합니다.

이를 만족하는 코드를 작성해봅시다.

// [0, arr.size())
vector<int> arr = {0, 1, 4, 8, 9};

int want_to_find = 4;
int begin = 0;
int end = arr.size(); // 가상의 값 위치, infinity

/*
begin == end인 경우 원소가 하나 뿐이고,
[begin, end]는 처음 true가 나타나는 위치를 포함하므로, begin == end == 찾는 위치 이므로 종료합니다.
*/
while(begin != end) {
    int mid = (begin + end) / 2;
    if(arr[mid] >= want_to_find) {
        end = mid; // end는 true임을 만족하며, 정렬되어 있으므로 [begin, end]는 처음 true가 나타난 위치를 포함합니다.
    } else {
        begin = mid + 1; // begin-1은 false이고, 정렬되어 있으므로 [begin, end]는 처음 true가 나타난 위치를 포함합니다.
    }
}

(begin + end)/2 는 floor되기 때문에 begin != end여서 mid < end입니다. 따라서 end = mid는 범위가 1 이상 줄어듭니다.
begin = mid + 1 은 mid + 1이기에 반드시 범위가 1이상 줄어듭니다.

좀 더 일반화해 predict(index) 함수가 처음 true인 위치를 찾는 함수를 작성해봅시다.

// in range [begin, end)
int lower_bound(int begin, int end)
{
    while(begin != end) {
        int mid = (begin + end) / 2;

        if(predict(mid)) {
            end = mid;
        } else {
            begin = mid + 1;
        }
    }

    return begin;
}

이렇게 [begin, end)꼴로 작성하면 뭘 반환할지 고민하지 않아도 됩니다.

사실 C++ 유저라면 std::lower_bound와 std::upper_bound를 사용하면 됩니다.
std::range::lower_bound(since C++20)를 이용하면 값 범위에 대한 탐색도 가능합니다.

#algorithm