이분탐색의 종료조건과 경계조건 정리

이분탐색의 종료조건과 경계조건, 즉 while문에 무엇이 들어가야 하는지, lo와 high를 각각 무슨 값으로 설정해야 하는지를 저를 포함해서 헷갈리시는 분들이 있는 거 같아서 한번 정리해 보려고 합니다.

우선 이분탐색의 기본 구조는 다음과 같습니다. (물론 이와 다르게 쓰셔도 상관없습니다)

int binary_search(int *arr, int key, int start, int end)
{
    int lo = /* */;
    int high = /* */;

    while (/* 1 */)
    {
        int mid = /* 2 */;

        if (arr[mid] == key)
            return mid;

        if (arr[mid] < key)
            /* 3 */
        else // arr[mid] > key
            /* 4 */
    }

    return -1;
}

lo, high에 대한 생각은 뒤로 미루어놓고, 1~4번에 들어갈 내용을 구체적인 코드로 적기 전에 문장으로 먼저 생각해 보겠습니다.

만약 우리가 탐색하는 배열 범위의 길이가 0이 되면, 원하는 데이터를 찾지 못했다는 것이고 while문에서 빠져나와야 합니다.

→ 탐색하는 배열 범위의 길이가 1 이상일 때

mid는 탐색하고자 하는 범위의 가운데를 가리킵니다.

→ (탐색 범위 시작점 + 탐색 범위 종점) / 2

여기서부터 나오는 "탐색 범위 시작점"과 "탐색 범위 종점"은 포함관계입니다. 즉, 탐색하고자 하는 배열의 인덱스를 i라 할 때 탐색 범위 시작점 <= i <= 탐색 범위 종점을 말합니다.

mid에 있는 원소가 찾고자 하는 값보다 작다는 것은, 찾고자 하는 값이 mid 오른쪽에 있다는 뜻입니다.

→ 탐색 범위를 mid < i <= 탐색 범위 종점으로 설정

반대로 찾고자 하는 값이 mid 왼쪽에 있다는 뜻입니다.

→ 탐색 범위를 탐색 범위 시작점 <= i < mid로 설정

int binary_search(int *arr, int key, int start, int end)
{
    int lo = /* */;
    int high = /* */;

    while (탐색하는 배열 범위의 길이가 1 이상일 때)
    {
        int mid = (탐색 범위 시작점 + 탐색 범위 종점) / 2;

        if (arr[mid] == key)
            return mid;

        if (arr[mid] < key)
            탐색 범위를 "mid < i <= 탐색 범위 종점"으로 설정;
        else
            탐색 범위를 "탐색 범위 시작점 <= i < mid"로 설정;
    }

    return -1;
}

각 문장에 들어갈 실제 코드는 lo와 high를 어떻게 설정하느냐에 따라 달라집니다.

1. 양쪽 포함: lo <= i <= high
2. lo 포함, high 미포함: lo <= i < high
3. lo 미포함, high 포함: lo < i <= high
4. 양쪽 미포함: lo < i < high

탐색해야 하는 배열의 전체 범위는 start <= i <= end이고, 이것을 lo <= i <= high로 표현하면:

lo = start, high = end

탐색 범위 시작점 = lo, 탐색 범위 종점 = high이므로:

mid = (lo + high) / 2

탐색 범위의 길이가 1 이상일 때를 lo와 high로 표현하면 lo <= high입니다.

• lo = 3, high = 3이면 → 범위는 3 <= i <= 3 → i = 3 → 길이 1 ✅
• lo = 4, high = 3이면 → 범위는 4 <= i <= 3 → 만족하는 i 없음 → 길이 0 ❌

while (lo <= high)

mid < i <= 종점으로 범위를 좁혀야 합니다. lo는 포함관계이므로, mid < i를 만족시키려면 lo = mid + 1로 설정하면 됩니다. → mid + 1 <= i <= high, 즉 mid < i <= high

lo = mid + 1

시작점 <= i < mid로 범위를 좁혀야 합니다. high는 포함관계이므로, i < mid를 만족시키려면 high = mid - 1로 설정하면 됩니다. → lo <= i <= mid - 1, 즉 lo <= i < mid

high = mid - 1

int binary_search(int *arr, int key, int start, int end)
{
    int lo = start;
    int high = end;

    while (lo <= high)
    {
        int mid = (lo + high) / 2;

        if (arr[mid] == key)
            return mid;

        if (arr[mid] < key)
            lo = mid + 1;
        else
            high = mid - 1;
    }

    return -1;
}

전체 범위 start <= i <= end를 lo <= i < high로 표현해야 합니다.

lo는 포함이므로 케이스 1과 동일하게 lo = start입니다. high는 미포함이므로, i < high가 i <= end와 같으려면 high = end + 1이어야 합니다.

lo = start, high = end + 1

앞서 정한 문장은 (탐색 범위 시작점 + 탐색 범위 종점) / 2였습니다.

시작점 = lo는 케이스 1과 동일하지만, 종점은 high가 아니라 high - 1입니다 (high는 미포함이므로).

mid = (lo + high - 1) / 2

• lo = 3, high = 4이면 → 범위는 3 <= i < 4 → i = 3 → 길이 1 ✅
• lo = 3, high = 3이면 → 범위는 3 <= i < 3 → 만족하는 i 없음 → 길이 0 ❌

while (lo < high)

lo는 포함관계이므로 케이스 1과 동일하게 lo = mid + 1입니다.

lo = mid + 1

케이스 1에서는 high가 포함관계라서 high = mid - 1로 1을 빼야 했지만, 여기서는 high가 미포함관계이므로 high = mid만 하면 i < mid가 만족됩니다. → lo <= i < high, 즉 lo <= i < mid

high = mid

int binary_search(int *arr, int key, int start, int end)
{
    int lo = start;
    int high = end + 1;

    while (lo < high)
    {
        int mid = (lo + high - 1) / 2;

        if (arr[mid] == key)
            return mid;

        if (arr[mid] < key)
            lo = mid + 1;
        else
            high = mid;
    }

    return -1;
}

케이스 3과 4는 자세한 설명은 생략하고 코드만 올리겠습니다.

int binary_search(int *arr, int key, int start, int end)
{
    int lo = start - 1;
    int high = end;

    while (lo < high) // ex) 3 < i <= 4 -> i = 4
    {
        int mid = (lo + high + 1) / 2;

        if (arr[mid] == key)
            return mid;

        if (arr[mid] < key)
            lo = mid;
        else
            high = mid - 1;
    }

    return -1;
}

int binary_search(int *arr, int key, int start, int end)
{
    int lo = start - 1;
    int high = end + 1;

    while (lo + 1 < high) // ex) 3 < i < 5 -> i = 4
    {
        int mid = (lo + high) / 2; // (lo + 1 + high - 1) / 2

        if (arr[mid] == key)
            return mid;

        if (arr[mid] < key)
            lo = mid;
        else
            high = mid;
    }

    return -1;
}

일반적으로는 어떤 케이스를 선택하든 문제가 없을겁니다. 다만 unsigned 타입(unsigned int, size_t 등)을 사용할 때는 케이스 2만 안전하게 사용할 수 있습니다.

케이스 3과 4는 lo = start - 1로 설정하기 때문에, start가 0이면 언더플로우가 발생합니다. 케이스 1도 high = mid - 1 때문에 언더플로우가 날 수 있습니다.

따라서 unsigned 타입을 쓰고 싶다면 케이스 2를 선택해야 합니다 (물론 다른 구현 방법도 있습니다). 실제로 libc의 bsearch 구현을 보면 케이스 2를 선택한 것을 알 수 있습니다. 소스코드

이런 식으로 빈칸에 들어갈 것들을 lo, high를 이용해서 코드를 넣기 전에 문장으로 먼저 생각해보고, lo와 high가 어떻게 설정되어 있는지에 따라 코드로 채워넣으면 헷갈리지 않고 이진탐색을 구현할 수 있지 않나 싶습니다.