binary_search
binary_search (정렬된 범위에서 이진 탐색)
정렬된 범위에서 특정 값을 이진 탐색으로 찾아 존재 여부만 판정하는 알고리즘이에요. 멤버를 찾기 위해서가 아니라 "있는지 없는지" 확인하는 게 목적이에요. <algorithm> 헤더에 있어요.
출처: cppreference
본문
binary_search는 범위 [first, last)에 value와 같은 원소가 있는지 확인해요. 범위는 비교 기준으로 정렬되어 있어야 해요.
template< class ForwardIt, class T >
bool binary_search( ForwardIt first, ForwardIt last,
const T& value ); // (1)
기본 버전은 operator<로 비교하고, comp를 받는 버전은 직접 비교기로 판단해요.
template< class ForwardIt, class T, class Compare >
bool binary_search( ForwardIt first, ForwardIt last,
const T& value, Compare comp ); // (2)
-
*it < value와value < *it가 모두 거짓인 원소가 있으면true.
-
comp(*it, value)와comp(value, *it)가 모두 거짓인 원소가 있으면true.
이런 이중 부정 판정 때문에 "같음"을 비교기의 관점에서 정의해요. 즉 범위의 어떤 원소가 value에 해당하면 true, 아니면 false를 반환해요.
복잡도는 std::distance(first, last)에 로그적인 비교 횟수, 최악의 경우 std::log2(last - first) + O(1)번이에요.
주의: lower_bound를 쓰면 존재 여부뿐 아니라 위치까지 알 수 있고, equal_range로는 같은 값의 전체 구간을 얻을 수 있어요. 단순 존재 확인만 필요하면 binary_search가 깔끔해요.
비교기는 std::sort에 쓴 것과 동일한 것을 전달해야 탐색이 정확해요. C++26부터 T의 기본값이 ForwardIt의 value_type으로 바뀌었어요.