C에서 이진 검색을 사용하여 요소 인덱스를 찾는 방법은 무엇입니까?

C에서 효율적인 이진 검색 구현

정렬된 컨테이너에서 요소의 인덱스 또는 반복자를 찾는 것은 C의 기본 작업입니다. 그러나 표준 라이브러리의 std::binary_search 알고리즘은 요소의 위치가 아닌 요소의 존재를 나타내는 부울만 반환합니다.

컨테이너가 정렬되는 경우를 고려하면 효율성을 위해 이진 검색 알고리즘이 바람직합니다. . 이러한 요구 사항을 해결하는 구현이 필요합니다.

사용자 정의 반복 이진 검색

한 가지 접근 방식은 사용자 정의 반복 이진 검색 알고리즘을 구현하는 것입니다. 구현 예는 다음과 같습니다.

<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::lower_bound를 사용하여 검색된 요소를 가리키는 반복자를 효율적으로 찾습니다. 찾은 값이 val과 일치하지 않으면 end() 반복자를 반환합니다.

대체 솔루션

또 다른 옵션은 std::set를 사용하는 것입니다. 요소 순서를 지정하고 지정된 항목에 대한 반복자를 반환하는 find(T 키) 메서드를 제공합니다. 다만, 중복된 요소가 필요한 경우에는 적합하지 않을 수 있습니다.

위 내용은 C에서 이진 검색을 사용하여 요소 인덱스를 찾는 방법은 무엇입니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!