Binary Search의 구현에 관한 정리. 주제 자체는 solved.ac 기준 실버 티어 정도일 수도 있겠지만, 제대로 쓰기까지 상당한 시간이 걸리는 주제이기도 하다. 또, 각종 알고리즘에서 뜬금없이 튀어나오는 1순위. O(n)을 O(log n)으로 줄여주는 강력한 무기.

TL;DR

Find

bool find(int v) {
    int l = 0; int r = N - 1;
    while (l <= r) {
        int m = (l + r) / 2; // overflow prevent: l + (r - l) / 2;
        if (arr[m] == v) return true;
        if (arr[m] < v) {
            l = m + 1;
        } else {
            r = m - 1;
        }
    }
    return false;
}

Lower Bound

int lb(int v) {
    int l = 0; int r = N - 1;
    int ans = -1;
    while (l <= r) {
        int m = (l + r) / 2; // overflow prevent: l + (r - l) / 2;
        if (arr[m] >= v) {
            r = m - 1;
            ans = m;
        } else {
            l = m + 1;
        }
    }
    return ans;
}

Upper Bound

int lb(int v) {
    int l = 0; int r = N - 1;
    int ans = -1;
    while (l <= r) {
        int m = (l + r) / 2; // overflow prevent: l + (r - l) / 2;
        if (arr[m] > v) {
            r = m - 1;
            ans = m;
        } else {
            l = m + 1;
        }
    }
    return ans;
}

알고리즘 정리

서론

Binary Search는 항상 구현이 헷갈린다. 범위를 어디까지 해야하는지, l, r 설정은 어떻게 해야하는지 등등…

여기서 그런 부분들을 한번 정리하고 넘어가고자 한다.

Binary Search의 STL 사용 구현

우선 표준이 되는 STL을 사용한 Binary Search 사용법을 확인해보자. 사용할 때 vector는 정렬이 되어 있어야 한다.

binary_search는 찾고자 하는 값이 있는지 없는지 여부를 반환한다.

bool isExist = binary_search(v.begin(), v.end(), tval);

lower_bound는 찾고자 하는 값보다 크거나 같은 값이 처음으로 나오는 시점을 반환한다. 반환값 형태는 iterator이다.

auto it = lower_bound(v.begin(), v.end(), tval);

upper_bound도 거의 동일하지만 크거나 같은 이 아닌 큰 이다. 사용법은 완전히 동일하다. (결과만 달라진다)

auto it = upper_bound(v.begin(), v.end(), tval);

Binary Search의 의의는 원소를 찾을 때 전체 원소(O(n))를 찾지 않아도 됨에 그 의의가 있다. 절반씩 찾을 원소가 줄어드므로 Master Theorem에 의해 시간복잡도가 O(log n)으로 줄어들게 된다.

Binary Search의 직접구현

직접 구현시에 신경써야 할 포인트들이 많이 있다.

loop시 l, r 조정 문제

오름차순으로 정렬된 arr[]에서, 원소를 찾으면 원소 index, 못찾으면 -1을 리턴하는 예시를 보자.

// [s, e] 구간 사용
int binarySearch(int arr[], int s, int e, int tval) {
    int l = s, int r = e, mid;
    while (l <= r) {
        mid = (l + r) >> 1;
        if (tval == arr[mid]) return mid;
        else if (tval < arr[mid]) {
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }
    return -1;
}

표로 하나 예시를 살펴보자.

index	0	1	2	3	4	5	6	7
value	5	8	10	14	17	20	22	25

이 경우, 10을 찾는다고 가정해보자.

첫번째 loop에서의 각 param 값은 아래와 같다.
- l: 0
- r: 7
- mid: 3
- 결과: arr[3] = 14 > 10 이므로, r 이 2로 조정된다.
두번째 loop는 아래와 같이 된다.
- l: 0
- r: 2
- mid: 1
- 결과: arr[1] = 8 > 10 이므로, l이 2로 조정된다.
세번째 loop는 l == r == 2이므로, 값을 찾고 종료된다.

즉, 오름차순 정렬된 배열 기준으로, 중앙을 봤을 때 그 값이 찾는 값보다 더 크면 타겟값은 좌측에 있을 것이라 생각할 수 있으므로 r이 조정되는 것이며, 반대의 경우 l이 조정된다고 할 수 있다.

lower_bound와 upper_bound의 실 구현

이 경우 더 분기를 줄이는 방법도 있지만, 구현이 쉬운 방법으로 아래처럼 binarySearch 함수를 변경해볼 수 있다.

// [s, e) 구간 사용
int lowerBound(int arr[], int s, int e, int tval) {
    int l = s, int r = e, mid, ans = e; // ans의 초기값에 유의
    while (l <= r) {
        mid = (l + r) >> 1;
        if (tval == arr[mid]) {
            ans = mid;
            r = mid - 1; // 만약 원소가 1 2 3 3 3 3 3 4 5 처럼 되어 있다면, 처음 찾은 3보다 더 왼쪽에 3이 또 있을 수 있다. 그래서 구간을 왼쪽으로 해서 계속 탐색한다.
        }
        else if (tval < arr[mid]) {
            ans = mid; // 여기에도 있어야 한다.
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }
    return ans;
}

lower_bound의 경우 위처럼만 수정하면 된다. 같을때 return 하는 것이 아니라 더 찾는 것이 포인트.

upper_bound는 아래처럼 해볼 수 있다.

// [s, e) 구간 사용
int upperBound(int arr[], int s, int e, int tval) {
    int l = s, int r = e, mid, ans = e; // ans의 초기값에 유의
    while (l <= r) {
        mid = (l + r) >> 1;
        if (tval == arr[mid]) { // lowerBound 구현 대비 달라지는 부분
            l = mid + 1; // 더 큰걸 찾는 거니까 좌측이 아닌 우측으로 계속해서 보면 된다. (lowerBound는 경계값에서 좌측, upper는 우측)
        }
        else if (tval < arr[mid]) {
            ans = mid;
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }
    return ans;
}

ans 를 업데이트 하는 부분만 변경되기 때문에 쉽게 확인해볼 수 있다. tval == arr[mid] 부분의 구현만 달라지고, 직관적으로 이해할 수 있다. lower_bound는 경계값을 업데이트 하지만, upper_bound는 아니다.

Time Complexity

Find: $O(\log N)$
LowerBound: $O(\log N)$
UpperBound: $O(\log N)$