C에서 반복자를 반환하는 이진 검색 알고리즘을 구현하는 방법은 무엇입니까?

C에서 반복자를 반환하는 이진 검색 알고리즘

C에서 std::binary_search 알고리즘은 편리한 방법을 제공합니다. 정렬된 컨테이너에 대해 이진 검색을 수행합니다. 그러나 요소가 존재하는지 여부를 나타내는 부울만 반환하므로 일부 애플리케이션에는 충분하지 않을 수 있습니다.

반복자 반환 알고리즘에 대한 요구 사항

다음에 대한 필요성이 발생합니다. 부울 대신 결과를 가리키는 반복자를 반환하는 이진 검색 알고리즘입니다. 이를 통해 개발자는 발견된 실제 요소에 액세스하거나 해당 요소가 컨테이너에 존재하지 않는지 확인할 수 있습니다.

사용자 정의 이진 검색 알고리즘 구현

해당 기능이 없기 때문에 표준 라이브러리에서 사용할 수 있으므로 std::lower_bound, std::upper_bound 또는 std::equal_range와 같은 다른 STL 함수를 사용하여 사용자 정의 구현을 만들 수 있습니다. .

샘플 구현

다음은 std::lower_bound:

<code class="cpp">template<class Iter, class T>
Iter binary_find(Iter begin, Iter end, T val)
{
    // Finds the lower bound in at most log(last - first) + 1 comparisons
    Iter i = std::lower_bound(begin, end, val);

    if (i != end &amp;&amp; !(val < *i))
        return i; // found
    else
        return end; // not found
}</code>

또는 std::set 사용

또 다른 옵션은 정렬된 요소를 유지하고 지정된 항목에 대한 반복자를 반환하는 find(T 키) 메서드를 제공하는 std::set를 사용하는 것입니다. . 그러나 컨테이너에 동일한 요소의 여러 인스턴스가 필요한 경우 이 접근 방식은 적합하지 않을 수 있습니다.

위 내용은 C에서 반복자를 반환하는 이진 검색 알고리즘을 구현하는 방법은 무엇입니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!