이진 탐색(Binary Search)

이진 탐색(Binary Search)

어떤 decision problem의 답이 단조성(monotonicity)를 띌 때, 정답을 포함하는 구간의 크기를 절반씩 줄여가며 query 횟수를 최대 O(logN)회로 제한할 수 있다.

mid보다 찾으려는 수가 작다면 mid의 오른쪽 원소들을 볼 필요가 없을 것이고, mid보다 찾으려는 수가 크다면 mid의 왼쪽 원소들도 볼 필요가 없을 것이다. divide-and-conquer 방식으로 접근해보자.

Devide

• arr[1..N]가 arr[1..mid]와 arr[mid..N]으로 divide.

Conquer

• A[mid] = x : return mid
• A[mid] < x : select A[mid + 1..N] for the next iteration.
• A[mid] > x : select A[1..mid - 1] for the next iteration.

Combine

• return the result.

핵심은 다음 iteration에서 배열을 절반 크기로 줄일 수 있다는 것이다.

코드로 구현하면 아래와 같다.

#include <iostream>
#include <iomanip>      // std::setw
#include <cassert>

using namespace std;

void PrintHelper(int* arr, int n, int left, int right)
{
    cout << "[" << left << "," << right << "]" << endl;

    cout << "Indices: ";
    for (int i = left; i <= right; i++)
        cout << setw(2) << i << " ";
    cout << endl;

    cout << "Values : " << setw(2);
    for (int i = left; i <= right; i++)
        cout << setw(2) << arr[i] << " ";
    cout << endl;
}

int BinarySearch(int* arr, int n, int x)
{
    int left = 0;
    int right = n - 1;

    while (left <= right)
    {
        PrintHelper(arr, n, left, right);

        int middle = (left + right) / 2 ; // 정수 나누기 (버림)

        cout <<  "middle " << middle << endl;

        if (x < arr[middle])
        {
            right = middle - 1;
            cout << "right " << right << endl;
        }
        else if (x > arr[middle])
        {
            left = middle + 1;
            cout << "left " << left << endl;
        }
        else
        {
            cout << "Found " << middle << endl;
            return middle;
        }
    }

    cout << "Not found" << endl;
    return -1; 
}

int main()
{
    int arr[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
    int n = sizeof(arr) / sizeof(arr[0]);

    assert(n > 0);

    BinarySearch(arr, n, 6);

    return 0;
}

output

[0,9]
Indices:  0  1  2  3  4  5  6  7  8  9 
Values :  0  1  2  3  4  5  6  7  8  9 
middle 4
left 5
[5,9]
Indices:  5  6  7  8  9 
Values :  5  6  7  8  9 
middle 7
right 6
[5,6]
Indices:  5  6 
Values :  5  6 
middle 5
left 6
[6,6]
Indices:  6 
Values :  6 
middle 6
Found 6