“유용한”C ++ 바이너리 검색 알고리즘은 어디서 구할 수 있습니까? API를 정의 할 때 도대체

std::binary_search표준 라이브러리의 <algorithm>헤더 와 같은 C ++ STL 컨테이너와 호환되는 이진 검색 알고리즘이 필요하지만 요소가 존재하는지 알려주는 단순한 부울이 아닌 결과를 가리키는 반복자를 반환해야합니다.

(참고로, 표준위원회가 binary_search 용 API를 정의 할 때 도대체 무슨 생각을했을까요?!)

여기서 내 주요 관심사는 바이너리 검색의 속도가 필요하다는 것입니다. 따라서 아래에 언급 된 것처럼 다른 알고리즘으로 데이터를 찾을 수 있지만 바이너리의 이점을 얻기 위해 데이터가 정렬되어 있다는 사실을 활용하고 싶습니다. 선형 검색이 아닌 검색입니다.

지금까지 lower_bound와 upper_bound데이텀이없는 경우 실패합니다 :

//lousy pseudo code
vector(1,2,3,4,6,7,8,9,0) //notice no 5
iter = lower_bound_or_upper_bound(start,end,5)
iter != 5 && iter !=end //not returning end as usual, instead it'll return 4 or 6

참고 : 컨테이너와 호환되는 한 std 네임 스페이스에 속하지 않는 알고리즘을 사용해도 괜찮습니다. 예를 들어, boost::binary_search.

답변

이 그러한 기능은 없지만, 당신은 사용하여 간단한 하나를 쓸 수 있습니다 std::lower_bound, std::upper_bound또는 std::equal_range.

간단한 구현은 다음과 같습니다.

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 && !(val < *i))
        return i; // found
    else
        return end; // not found
}

또 다른 해결책은 std::set요소의 순서를 보장 iterator find(T key)하고 주어진 항목에 반복기를 반환하는 메서드 를 제공 하는를 사용하는 것입니다. 그러나 요구 사항이 집합 사용과 호환되지 않을 수 있습니다 (예 : 동일한 요소를 여러 번 저장해야하는 경우).

답변

를 봐야 std::equal_range합니다. 모든 결과의 범위에 대해 한 쌍의 반복자를 반환합니다.

답변

그 세트가 있습니다.

http://www.sgi.com/tech/stl/table_of_contents.html

검색 :

별도의 참고 :

그들은 아마도 컨테이너를 검색하면 하나 이상의 결과를 검색 할 수 있다고 생각했을 것입니다. 그러나 존재 여부를 테스트해야하는 이상한 경우에는 최적화 된 버전도 좋을 것입니다.

답변

std :: lower_bound가 원하는 수준에 비해 너무 낮은 경우 boost :: container :: flat_multiset 을 확인하는 것이 좋습니다 . 이진 검색을 사용하여 정렬 된 벡터로 구현 된 std :: multiset의 드롭 인 대체입니다.

답변

표준 라이브러리에 포함되지 않은 이유를 궁금해하는 가장 짧은 구현 :

template<class ForwardIt, class T, class Compare=std::less<>>
ForwardIt binary_find(ForwardIt first, ForwardIt last, const T& value, Compare comp={})
{
    // Note: BOTH type T and the type after ForwardIt is dereferenced 
    // must be implicitly convertible to BOTH Type1 and Type2, used in Compare. 
    // This is stricter than lower_bound requirement (see above)

    first = std::lower_bound(first, last, value, comp);
    return first != last && !comp(value, *first) ? first : last;
}

에서 https://en.cppreference.com/w/cpp/algorithm/lower_bound

답변

이 기능을 확인하십시오. qBinaryFind :

RandomAccessIterator qBinaryFind ( RandomAccessIterator begin, RandomAccessIterator end, const T & value )

범위 (시작, 끝)의 이진 검색을 수행하고 값이 발생한 위치를 반환합니다. 값이 없으면 end를 반환합니다.

[시작, 끝) 범위의 항목은 오름차순으로 정렬해야합니다. qSort ()를 참조하십시오.

동일한 값이 많이 발생하면 그중 하나가 반환 될 수 있습니다. 더 세밀한 제어가 필요한 경우 qLowerBound () 또는 qUpperBound ()를 사용하십시오.

예:

QVector<int> vect;
 vect << 3 << 3 << 6 << 6 << 6 << 8;

 QVector<int>::iterator i =
         qBinaryFind(vect.begin(), vect.end(), 6);
 // i == vect.begin() + 2 (or 3 or 4)

이 함수는 Qt 라이브러리 <QtAlgorithms>의 일부인 헤더에 포함되어 있습니다.

답변

std :: lower_bound () 🙂