이진 탐색이란?

본 블로그 작성 글들은, 강의를 목표로 하고 제작되었습니다. 또한 작성된 글의 정보도 틀렸을 수 있으니, 주의해주세요.

Binary Search(이진 탐색)는 정렬된 범위의 가운데 값을 확인하고 탐색 구간을 절반씩 줄인다.

1 3 5 7 9 11 13
      ↑ 7 확인

11을 찾으려면 오른쪽 절반만 남긴다.

기본 구현

int BinarySearch(const std::vector<int>& Values, int Target)
{
    int Left = 0;
    int Right = static_cast<int>(Values.size()) - 1;

    while (Left <= Right)
    {
        const int Middle = Left + (Right - Left) / 2;

        if (Values[Middle] == Target)
        {
            return Middle;
        }

        if (Values[Middle] < Target)
        {
            Left = Middle + 1;
        }
        else
        {
            Right = Middle - 1;
        }
    }

    return -1;
}

매번 범위가 절반이 되므로 시간 복잡도는 O(log N)이다.

반드시 정렬되어 있어야 한다

정렬되지 않은 데이터에 이진 탐색을 적용하면 어느 절반을 버려도 되는지 판단할 수 없다. 탐색할 때마다 먼저 정렬한다면 정렬 비용도 같이 계산해야 한다.

첫 번째 같은 값, 마지막 같은 값, 값이 들어갈 위치를 찾는 문제는 경계 조건이 조금씩 다르다. C++에서는 std::lower_bound와 std::upper_bound를 사용하면 이런 경계를 안전하게 구할 수 있다.

이진 탐색의 어려운 부분은 가운데 값을 찾는 일이 아니다. 현재 범위가 닫힌 구간인지 반열린 구간인지 끝까지 같은 규칙을 유지하는 것이다.