algorithm_binary_search
algorithm_binary_search (이진 탐색)
std::binary_search는 파티셔닝된 정렬 범위 [first, last)에서 value와 동등한 요소가 존재하는지 검사해요. 요소가 있는지 유무만 알려주고, 위치를 찾아주진 않아요.
출처: cppreference
본문
std::binary_search는 value에 동등한 요소가 파티셔닝된 소스 범위 [first, last)에 존재하는지 확인해요. 어떤 요소는 value보다 앞서지도 않고 뒤서지도 않을 때 value와 동등하다고 간주돼요. <algorithm> 헤더에 정의되어 있어요.
template< class ForwardIt, class T >
bool binary_search( ForwardIt first, ForwardIt last,
const T& value );
template< class ForwardIt, class T, class Compare >
bool binary_search( ForwardIt first, ForwardIt last,
const T& value, Compare comp );
- 1번 오버로드 — 순서는
operator<(즉std::less{})로 결정돼요. 표현식bool(e < value)와bool(value < e)를 기준으로 파티셔닝돼 있어야 해요. - 2번 오버로드 — 순서는 비교 함수
comp로 결정돼요. 표현식bool(comp(e, value))와bool(comp(value, e))를 기준으로 파티셔닝돼 있어야 해요.
다음 조건이 만족되면 동작이 정의되지 않아요: 소스 범위의 요소들이 위 두 표현식에 대해 동시에 파티셔닝되어 있지 않거나, 그 두 표현식이 다른 값을 내는 요소가 존재하는 경우예요.
반환값 (Return value)
value에 동등한 요소가 존재하면 true, 아니면 false예요.
복잡도 (Complexity)
N을 std::distance(first, last)라고 하면 log₂(N) + 𝓞(1)번 이하의 비교가 필요해요. ForwardIt이 RandomAccessIterator가 아니라면 반복자 증가 횟수는 std::distance(first, last)에 선형이에요.
참고 (Notes)
std::binary_search는 소스 범위가 파티셔닝만 되어 있으면 되지만, 보통 정렬된 범위에서 사용해요. 동등한 요소의 위치를 얻으려면 std::lower_bound를 사용해야 해요.
예제 (Example)
#include <algorithm>
#include <cassert>
#include <complex>
#include <iostream>
#include <vector>
int main()
{
const auto haystack = {1, 3, 4, 5, 9};
for (const auto needle : {1, 2, 3})
{
std::cout << "Searching for " << needle << '\n';
if (std::binary_search(haystack.begin(), haystack.end(), needle))
std::cout << "Found " << needle << '\n';
else
std::cout << "Not found!\n";
}
using CD = std::complex<double>;
std::vector<CD> nums{{1, 1}, {2, 3}, {4, 2}, {4, 3}};
auto cmpz = [](CD x, CD y){ return abs(x) < abs(y); };
assert(std::binary_search(nums.cbegin(), nums.cend(), CD{4, 2}, cmpz));
}
출력:
Searching for 1
Found 1
Searching for 2
Not found!
Searching for 3
Found 3
가능한 구현 (Possible implementation)
template<class ForwardIt, class T = typename std::iterator_traits<ForwardIt>::value_type>
bool binary_search(ForwardIt first, ForwardIt last, const T& value)
{
return std::binary_search(first, last, value, std::less{});
}
template<class ForwardIt, class T = typename std::iterator_traits<ForwardIt>::value_type,
class Compare>
bool binary_search(ForwardIt first, ForwardIt last, const T& value, Compare comp)
{
first = std::lower_bound(first, last, value, comp);
return (!(first == last) and !(comp(value, *first)));
}