[Algorithm/Divide&Conquer] 02. 이진 검색(binary search)

이진 검색(binary search) (a.k.a 이진 탐색)

 

일반적인 검색 문제

정렬되어 있는 정수 시퀀스가 있고, 여기에 숫자 N이 있는지 확인하려고 한다.

이러한 검색 문제는 두 가지 방법으로 접근할 수 있다. 

 

선형 검색(linear search)

시퀀스 전체 원소를 방문하면서 해당 원소가 N과 같은지를 확인하는 방식이다.

bool linear_search(int n, vector<int>& sequence) {
    for (auto i : sequence) {
        if (i == n) {
            return true;
        }
    }
    return false;
}

 

• 장점 : 입력 시퀀스의 정렬 여부와 상관 없이 항상 잘 동작한다
• 단점 : 효율적이지 않음.
  • O(N)
• 주어진 배열이 정렬되어있는 경우 정렬되어 있다는 점을 이용하지 못함

 

이진 검색(binary search)

주어진 시퀀스가 정렬되어 있다는 사실을 이용해보자

1. 전체 시퀀스 범위를 range로 설정
2. range의 가운데 원소를 M이라고 하고, M과 N을 비교
3. M==N이면 시퀀스에서 N을 찾은 것이므로 검색을 중단
4. 그렇지 않으면 아래 두 규칙에 따라 range를 수정
   1. 만약 N<M 이면 N은 M의 왼쪽에 있을 것으로 예상할 수 있고, range에서 M의 오른쪽에 있는 모든 원소는 제거한다
   2. 반대로 N>M이면 range에서 M의 왼쪽에 있는 모든 원소를 제거한다
5. 만약 range에 한 개보다 많은 원소가 남이있다면 2단계로 이동한다
6. 그렇지 않으면 주어진 시퀀스에 N이 존재하지 않는 것이며, 검색을 종료한다

bool binary_search(int n, std::vector<int>& sequence) {
    auto first = sequence.begin();
    auto last = sequence.end();
    while (true) {
        auto range_length = std::distance(first, last);
        auto mid_index = std::floor(range_length / 2);
        auto mid_element = *(first + mid_index);
        // mid_element와 N 값을 비교
        if (mid_element == n) {
            return true;
        }
        else if (mid_element > n) {
            std::advance(last, -mid_element);
        }
        else {
            std::advance(first, mid_element);
        }

        if (range_length == 1)
            return false;
    }
}

 

 

std::distance와 std::advance에 대한 설명은 다음을 참조