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;
}
답변
이 기능을 확인하십시오. 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 () 🙂