C++ STL 바이너리 검색

std::binary_search는 정렬된 범위에 특정 값이 있는지 확인할 때 사용합니다. 이 함수는 값의 존재 여부를 Boolean으로 반환하며, 일치하는 반복자나 일치하는 값의 개수를 반환하지는 않습니다. 정렬 조건이 충족되고 적절한 반복자를 사용할 수 있다면 vector, 배열 또는 다른 범위에도 적용할 수 있습니다.

std::binary_search의 요구 사항 이해하기

검색 범위는 검색에서 사용하는 비교 기준에 따라 분할되어 있어야 합니다. 일반적인 사용에서는 기본 비교와 같은 순서로 원소를 오름차순 정렬해야 합니다. 범위가 그 순서로 정렬되어 있지 않으면 값의 존재 여부를 신뢰성 있게 판단할 수 없습니다. 한 번 정렬한 뒤 원소를 변경하거나 일부만 수정해도 이 전제 조건이 깨질 수 있습니다.

반복자 쌍은 반열린 범위인 [first, last)를 나타냅니다. first는 검색에 포함되는 첫 원소를 가리키고, last는 마지막 원소 바로 다음을 가리키므로 범위에서 제외됩니다. container.begin()과 container.end()를 전달하면 컨테이너 전체를 검색합니다. 빈 범위도 유효하며 일치하는 값이 없다고 판단합니다. 원소가 하나인 범위에서는 first가 그 원소를 가리키고 last가 그 다음을 가리키면 해당 원소가 검색 대상에 포함됩니다.

검색 기준에 따라 동등한 원소가 있으면 결과는 true이고, 없으면 false입니다. 위치가 필요하다면 std::lower_bound 같은 연산을 사용한 뒤 반환된 반복자가 last가 아닌지, 값이 검색 기준에 따라 동등한지 확인하세요. std::binary_search만으로는 중복 원소 중 어느 것이 일치했는지 알 수 없습니다.

정렬된 범위에서 std::binary_search 사용하기

함수를 사용하려면 <algorithm>, 출력을 위해서는 <iostream>, 이 예제의 컨테이너를 위해서는 <vector>를 포함하세요. 다음 완전한 프로그램은 범위에 있는 값 하나와 없는 값 하나를 확인합니다. Boolean 결과를 직접 사용하므로 반복자에 의존하지 않고 두 경우를 확인할 수 있습니다.

예제를 실행해 보세요. 코드와 출력의 6 found: 및 7 found: 레이블은 바이트 동일성 규칙에 따라 영어로 유지됩니다.

#include <algorithm>
#include <iostream>
#include <vector>

int main() {
    const std::vector<int> values{2, 4, 6, 8, 10};
    const bool has_six = std::binary_search(values.begin(), values.end(), 6);
    const bool has_seven = std::binary_search(values.begin(), values.end(), 7);

    std::cout << std::boolalpha
              << "6 found: " << has_six << '\n'
              << "7 found: " << has_seven << '\n';
}

6 found: true
7 found: false

vector는 이미 정렬되어 있으며 각 호출에는 전체 반복자 범위가 전달됩니다. 예제를 응용하려면 검색 대상을 바꾸세요. 이때 vector는 검색에서 기대하는 것과 같은 순서를 유지해야 합니다. 함수가 범위를 대신 정렬해 주지는 않습니다.

사용자 지정 비교자로 검색하기

사용자 정의 타입을 검색할 때는 범위의 정렬 순서를 정의하는 비교자를 전달하세요. 검색 전에 같은 비교자를 사용해 범위를 정렬해야 합니다. 이 예제에서는 레코드를 나이순으로 정렬하고, 같은 나이의 레코드가 있으면 검색 대상이 있다고 판단합니다. 이 비교 기준에서는 이름을 동일성 판단에 사용하지 않습니다.

이 섹션의 코드와 표시되는 레이블 또는 출력은 영어로 유지됩니다.

#include <algorithm>
#include <string>
#include <vector>

struct Person {
    std::string name;
    int age;
};

int main() {
    const auto by_age = [](const Person& left, const Person& right) {
        return left.age < right.age;
    };

    std::vector<Person> people{{"Alice", 30}, {"Bob", 25}, {"Charlie", 35}};
    std::sort(people.begin(), people.end(), by_age);

    const Person target{"", 25};
    const bool found = std::binary_search(
        people.begin(), people.end(), target, by_age);
    return found ? 0 : 1;
}

비교자는 반복자가 아니라 값을 비교합니다. 범위를 정렬할 때 사용한 순서를 제공해야 하며, 범위의 원소와 검색 대상 사이의 비교에도 호환되어야 합니다. 여기서는 이름이 달라도 나이가 같으면 두 레코드를 검색 기준상 동등하게 취급합니다. 애플리케이션에서 그런 레코드를 구분해야 한다면 구분에 필요한 필드를 정렬 기준에 포함하거나 다른 검색 방법을 사용하세요.

이진 검색에서 흔히 하는 실수 피하기

• 정렬되지 않은 데이터 검색: 먼저 범위를 정렬하세요. 한 기준으로 정렬하고 다른 기준으로 검색하면 검색 요건을 충족하지 못합니다.
• last를 원소로 취급: last는 범위에서 제외됩니다. 컨테이너 전체를 검색할 때는 container.end()를 사용하고 역참조하지 마세요.
• 반복자를 기대: 반환형은 Boolean입니다. 위치가 필요하면 std::lower_bound를 사용하고 역참조하기 전에 결과를 확인하세요.
• 서로 맞지 않는 비교자 사용: 정렬과 검색에서 순서와 동등성 기준이 일치해야 합니다. 비교자가 두 레코드를 동등하게 취급하면 모든 필드가 아니라 그 기준에 따른 존재 여부를 판단합니다.

이 점들을 지키면 함수의 결과를 올바르게 해석할 수 있습니다. 라이브러리가 검색을 수행하지만, 범위가 다른 순서로 준비되었거나 비교자가 데이터와 맞지 않는다는 사실까지 감지하지는 못합니다.