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.