요소의 위치를 ​​반환하는 C에서 이진 검색 알고리즘을 구현하는 방법은 무엇입니까?

"유용한" C 바이너리 검색 알고리즘 얻기

C STL은 바이너리 검색 알고리즘을 제공하지만, 요소가 존재합니다. 요소의 정확한 위치가 필요한 경우에는 보다 포괄적인 알고리즘이 필요합니다.

한 가지 옵션은 사용자 정의 이진 검색 기능을 만드는 것입니다. 다음은 간단한 구현입니다.

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

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

또 다른 접근 방식은 요소를 자동으로 정렬하고 항목에 대한 반복자를 반환하는 find(T 키) 메서드를 제공하는 std::set를 사용하는 것입니다. 그러나 데이터에 중복된 값이 포함될 수 있는 경우에는 적합하지 않을 수 있습니다.

속도가 중요한 상황에서는 이진 검색의 이점을 활용하는 것이 중요합니다. Lower_bound 및 upper_bound 알고리즘은 요소가 존재하지 않는 경우 최종 반복자를 반환하지 않을 수 있으므로 부적절할 수 있습니다. 위에 제공된 bin_find 함수는 이 문제를 해결하고 올바른 동작을 보장합니다.

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