binary_search

아티클
06/09/2015

지정된 값과 같거나 이진 조건자가 지정되었다는 의미에서 동일한 정렬된 범위에 요소가 있는지 여부를 테스트합니다.

template<class ForwardIterator, class Type> 
   bool binary_search( 
      ForwardIterator first,  
      ForwardIterator last, 
      const Type& value 
   ); 
template<class ForwardIterator, class Type, class BinaryPredicate> 
   bool binary_search( 
      ForwardIterator first,  
      ForwardIterator last, 
      const Type& value,  
      BinaryPredicate comp 
   );

매개 변수

first
검색할 범위에 있는 첫 번째 요소의 위치를 가리키는 정방향 반복기입니다.
last
검색할 범위에 있는 마지막 요소의 하나 뒤 위치를 가리키는 정방향 반복기입니다.
value
요소의 값과 일치하는 데 필요한 값 또는 이진 조건자가 지정하는 요소 값으로 조건을 만족해야 하는 값입니다.
comp
한 요소가 다른 요소보다 작은 개념을 정의하는 사용자 정의 조건자 함수 개체입니다. 이진 조건자는 두 개의 인수를 사용하고 만족할 때는 true를 만족하지 못할 때는 false를 반환합니다.

반환 값

지정된 값과 같거나 이에 해당하는 범위에서 요소가 발견되는 경우 true이고 그렇지 않으면 false입니다.

설명

참조된 정렬된 소스 범위는 유효해야 하며 모든 포인터는 역참조할 수 있어야 하고 시퀀스 내에서 마지막 위치는 처음부터 증분 만큼 접근할 수 있어야 합니다.

정렬된 범위는 조합된 범위 정렬을 위해 알고리즘에서 사용하는 동일한 순서 지정에 따라 binary_search 알고리즘 적용에 대한 전제 조건으로 각각 정렬되어야 합니다.

소스 범위는 binary_search으로 수정되지 않습니다.

정방향 반복기의 값 형식은 순서가 지정될 비교 가능한 값보다 작아야 합니다. 제공된 두 개 요소에서 두 요소가 동일하거나(어떤 것도 다른 것보다 작지 않음) 하나가 다른 것보다 작음을 정할 수 있습니다. 그러면 동일하지 않은 요소 사이에 정렬이 수행됩니다.

알고리즘의 복잡성은 임의 액세스 반복기 및 선형에 대한 로그이며 반대의 경우는 비례하는 단계의 수(last – first)입니다.

예제

// alg_bin_srch.cpp
// compile with: /EHsc
#include <list>
#include <vector>
#include <algorithm>
#include <functional>      // greater<int>( )
#include <iostream>

// Return whether modulus of elem1 is less than modulus of elem2
bool mod_lesser( int elem1, int elem2 )
{
    if (elem1 < 0)
        elem1 = - elem1;
    if (elem2 < 0)
        elem2 = - elem2;
    return elem1 < elem2;
}

int main( )
{
    using namespace std;

    list <int> List1;

    List1.push_back( 50 );
    List1.push_back( 10 );
    List1.push_back( 30 );
    List1.push_back( 20 );
    List1.push_back( 25 );
    List1.push_back( 5 );

    List1.sort();

    cout << "List1 = ( " ;
    for ( auto Iter : List1 )
        cout << Iter << " ";
    cout << ")" << endl;

    // default binary search for 10
    if( binary_search(List1.begin(), List1.end(), 10) )
        cout << "There is an element in list List1 with a value equal to 10."
        << endl;
    else
        cout << "There is no element in list List1 with a value equal to 10."
        << endl;

    // a binary_search under the binary predicate greater
    List1.sort(greater<int>());
    if( binary_search(List1.begin(), List1.end(), 10, greater<int>()) )
        cout << "There is an element in list List1 with a value greater than 10 "
        << "under greater than." << endl;
    else
        cout << "No element in list List1 with a value greater than 10 "
        << "under greater than." << endl;

    // a binary_search under the user-defined binary predicate mod_lesser
    vector<int> v1;

    for( auto i = -2; i <= 4; ++i )
    {
        v1.push_back(i);
    }

    sort(v1.begin(), v1.end(), mod_lesser);

    cout << "Ordered using mod_lesser, vector v1 = ( " ;
    for( auto Iter : v1 )
        cout << Iter << " ";
    cout << ")" << endl;

    if( binary_search(v1.begin(), v1.end(), -3, mod_lesser) )
        cout << "There is an element with a value equivalent to -3 "
        << "under mod_lesser." << endl;
    else
        cout << "There is not an element with a value equivalent to -3 "
        << "under mod_lesser." << endl;
}

Output

List1 = ( 5 10 20 25 30 50 )
There is an element in list List1 with a value equal to 10.
There is an element in list List1 with a value greater than 10 under greater than.
Ordered using mod_lesser, vector v1 = ( 0 -1 1 -2 2 3 4 )
There is an element with a value equivalent to -3 under mod_lesser.