binary_search

测试在有序范围内是否存在与指定值相等或在某种意义上等效于二进制谓词指定下的值的一个元素。

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.

要求

标头： <算法>

命名空间: std

请参见

参考

lower_bound

upper_bound

equal_range

标准模板库