Namespaces
Variants

    std::binary_search

    cppreference.net에서
     
    C++
     
    알고리즘 라이브러리
    제약 조건이 있는 알고리즘 및 범위에 대한 알고리즘 (C++20)
    제약 조건이 있는 알고리즘, 예: ranges::copy, ranges::sort, ...
    정렬 및 관련 연산
    분할 연산
    (C++11)    
    (C++11)

    정렬 연산
    이진 탐색 연산
    (분할된 범위에 대해)
    집합 연산 (정렬된 범위에 대해)
    병합 연산 (정렬된 범위에 대해)
    힙 연산
    최소/최대 연산
    (C++11)
    (C++17)
    사전식 비교 연산
    (C++20)
    순열 연산


     
    헤더 <algorithm> 
    template< class ForwardIt, class T >
bool binary_search( ForwardIt first, ForwardIt last,
                    const T& value );
    		에 정의됨 (1) (C++26까지)
    (C++20부터 constexpr)    		 
    template< class ForwardIt, class T = typename std::iterator_traits
                                         <ForwardIt>::value_type >
constexpr bool binary_search( ForwardIt first, ForwardIt last,
                              const T& value );
    		(C++26부터) 
    template< class ForwardIt, class T, class Compare >
bool binary_search( ForwardIt first, ForwardIt last,
                    const T& value, Compare comp );
    		(2) (C++26까지)
    (C++20부터 constexpr)    		 
    template< class ForwardIt, class T = typename std::iterator_traits
                                         <ForwardIt>::value_type,
          class Compare >
constexpr bool binary_search( ForwardIt first, ForwardIt last,
                              const T& value, Compare comp );
    		(C++26부터)

    분할된 범위 value 내에 [first, last) 와(과) 동등한 요소가 있는지 확인합니다.

    1) 동등성은 operator< 을(를) 사용하여 확인합니다:

    !bool(*iter < value) && !bool(value < *iter) 이(가) true 의 어떤 반복자 iter 에 대해 [first, last) 인 경우, true 을(를) 반환합니다. 그렇지 않으면 false 을(를) 반환합니다.

    다음 조건 중 하나라도 충족되면 동작이 정의되지 않습니다:

    • elem 의 임의의 요소 [first, last) 에 대해, bool(elem < value) 이(가) !bool(value < elem) 을(를) 의미하지 않습니다.
    • elem 의 요소 [first, last) 는 분할되어 있지 않습니다bool(elem < value) 와(과) !bool(value < elem) 표현식에 대해.
    		 (C++20까지)

    std::binary_search(first, last, value, std::less{}) 와(과) 동일합니다.

    		(C++20부터)
    2) 동등성은 comp 을(를) 사용하여 확인합니다:
    !bool(comp(*iter, value)) && !bool(comp(value, *iter)) 이(가) true 의 어떤 반복자 iter 에 대해 [first, last) 인 경우, true 을(를) 반환합니다. 그렇지 않으면 false 을(를) 반환합니다.
    다음 조건 중 하나라도 충족되면 동작이 정의되지 않습니다:
    • elem 의 임의의 요소 [first, last) 에 대해, bool(comp(elem, value)) 이(가) !bool(comp(value, elem)) 을(를) 의미하지 않습니다.
    • elem 의 요소 [first, last) 는 분할되어 있지 않습니다bool(comp(elem, value)) 와(과) !bool(comp(value, elem)) 표현식에 대해.

    매개변수

    first, last - 검사할 분할된 범위의 요소를 정의하는 반복자 쌍
    value - 요소를 비교할 값
    comp - 첫 번째 인수가 두 번째보다 앞서 정렬되면 ​true 을(를) 반환하는 이진 술어.

    술어 함수의 시그니처는 다음과 동등해야 합니다:

    bool pred(const Type1 &a, const Type2 &b);

    시그니처에 const & 이(가) 있을 필요는 없지만, 함수는 전달된 객체를 수정하지 않아야 하며 (const) Type1 및 Type2 유형의 모든 값을 값 범주와 관계없이 받을 수 있어야 합니다 (따라서 Type1 & 은(는) 허용되지 않으며, Type1 도 이동이 복사와 동등한 경우가 아니면 허용되지 않습니다Type1(C++11부터)).
    Type1 및 Type2 유형은 T 유형의 객체가 Type1 및 Type2 모두로 암시적으로 변환될 수 있고, ForwardIt 유형의 객체가 역참조된 후 Type1 및 Type2 모두로 암시적으로 변환될 수 있도록 해야 합니다. ​

    유형 요구 사항
    -
    ForwardIt 는 LegacyForwardIterator 의 요구 사항을 충족해야 합니다.
    -
    Compare 는 BinaryPredicate 의 요구 사항을 충족해야 합니다. Compare 를 만족할 필요는 없습니다.

    반환값

    truevalue 와(과) 동등한 요소가 발견되면 false , 그렇지 않으면

    .

    복잡도N 을(를) std::distance(first, last) 로 정의할 때:

    1) 최대 log2(N)+O(1) 번의 value 비교 (operator< 사용)(C++20까지)std::less{}(C++20부터).
    2) 최대 log2(N)+O(1) 번의 비교자 comp 적용.

    단, ForwardIt 이(가) LegacyRandomAccessIterator 가 아닌 경우, 반복자 증가 횟수는 N 에 선형입니다.

    비고

    std::binary_search 은(는) [first, last) 이(가) 분할되기만 하면 되지만, 이 알고리즘은 일반적으로 [first, last) 이(가) 정렬된 경우에 사용되어 이진 탐색이 임의의 value 에 대해 유효합니다.

    std::binary_search 은(는) 동등한 요소가 존재하는지만 확인합니다. 해당 요소에 대한 반복자를 얻으려면 (존재하는 경우) std::lower_bound 를 대신 사용해야 합니다.

    기능 테스트 매크로 값 표준 기능
    __cpp_lib_algorithm_default_value_type 202403 (C++26) 알고리즘을 위한 초기화 리스트 (1,2)

    가능한 구현

    libstdc++ 및 libc++의 구현도 참고하십시오.

    binary_search (1) 
    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{});
}
    binary_search (2) 
    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)));
}

    예제

    이 코드 실행
    #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); };
    #ifdef __cpp_lib_algorithm_default_value_type
        assert(std::binary_search(nums.cbegin(), nums.cend(), {4, 2}, cmpz));
    #else
        assert(std::binary_search(nums.cbegin(), nums.cend(), CD{4, 2}, cmpz));
    #endif
}

    출력: 

    Searching for 1
Found 1
Searching for 2
Not found!
Searching for 3
Found 3

    결함 보고서

    다음 동작 변경 결함 보고서는 이전에 게시된 C++ 표준에 소급하여 적용되었습니다.

    DR 적용 대상 게시된 동작 올바른 동작
    LWG 270 C++98 Compare 는 Compare 를 만족해야 하며 T 는
    LessThanComparable 여야 했습니다 (엄격한 약순서 필요)     		분할만 필요;
    이종 비교 허용
    LWG 787 C++98 최대 log2(N)+2 번의 비교가 허용되었습니다 log2(N)+O(1)

    로 수정됨

    		 equal_range
    이진 탐색을 사용하여 주어진 값과 일치하는 요소의 범위를 찾습니다&(함수 템플릿
    ranges::equal_range
    		lower_bound
    이진 탐색을 사용하여 주어진 값보다 작지 않은 첫 번째 요소를 찾습니다&(함수 템플릿
    ranges::lower_bound
    		upper_bound
    이진 탐색을 사용하여 주어진 값보다 큰 첫 번째 요소를 찾습니다&(함수 템플릿
    ranges::upper_bound
    ranges::binary_search
    		 (C++20)
    이진 탐색을 사용하여 요소가 범위에 존재하는지 확인합니다
    (알고리즘 함수 객체)