C에서 효율적인 이진 검색 알고리즘 검색

프로그래머는 대수 시간 복잡도의 이점을 제공하는 효율적인 이진 검색 알고리즘을 구현하려고 하는 경우가 많습니다. . 일반적인 요구 사항 중 하나는 알고리즘이 검색 결과의 존재를 나타내는 단순한 부울 대신 검색 결과를 가리키는 반복자를 반환하는 것입니다.

C 표준 라이브러리는 헤더에 std::binary_search를 제공하지만 부울을 반환합니다. 질문자가 지적한 바와 같이, 이는 이진 검색의 속도가 요구되고 데이터가 정렬된 것으로 알려진 상황에서는 실망스러울 수 있습니다.

다행히도 원하는 기능을 제공하는 대체 구현이 있습니다. 널리 사용되는 옵션 중 하나는 std::lower_bound, std::upper_bound 또는 std::equal_range 함수를 활용하는 사용자 지정 알고리즘을 사용하는 것입니다. 다음은 이러한 구현의 단순화된 버전입니다.

template
Iter binary_find(Iter begin, Iter end, T val) {
    // Determine the lower bound using binary search
    Iter i = std::lower_bound(begin, end, val);

    // If the element is found, return the iterator to it
    if (i != end && !(val 
또는 요소의 순서를 보장하고 원하는 항목에 대한 반복자를 반환하는 find 메서드를 제공하는 std::set를 사용할 수 있습니다. 그러나 특히 동일한 요소의 여러 인스턴스를 저장해야 하는 경우 요구 사항이 집합 사용과 호환되는지 고려하는 것이 중요합니다.