STL algorithm算法binary_search(5)

原文地址：http://www.cplusplus.com/reference/algorithm/binary_search/

function template

<algorithm>

std::binary_search

default (1)custom (2)

template <class ForwardIterator, class T>
  bool binary_search (ForwardIterator first, ForwardIterator last,
                      const T& val);

template <class ForwardIterator, class T, class Compare>
  bool binary_search (ForwardIterator first, ForwardIterator last,
                      const T& val, Compare comp);

Test if value exists in sorted sequence

Returnstrueif any element in the range[first,last)is equivalent toval, andfalseotherwise.

如果在[first,end)范围内存在任一元素和val相等，则返回true,否则返回false.

例子：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void binary_s(){

    vector<int> vi;
    for(int i=0;i<9;i++)
        vi.push_back(i);


    if(binary_search(vi.begin(),vi.end(),1))
        cout<<"1 exits!"<<endl;
    else
        cout<<"1 didn't exits!"<<endl;


    if(binary_search(vi.begin(),vi.end(),7))
        cout<<"7 exits!"<<endl;
    else
        cout<<"7 didn't exits!"<<endl;

    if(binary_search(vi.begin(),vi.end(),10))
        cout<<"10 exits!"<<endl;
    else
        cout<<"10 didn't exits!"<<endl;


}

运行截图：

The elements are compared usingoperator<for the first version, andcompfor the second. Two elements,aandbare considered equivalent if(!(a<b) && !(b<a))or if(!comp(a,b) && !comp(b,a)).

第一个版本里面元素的比较使用<比较符。第二个个使用comp比较器，两个元素，a和b相等的条件为(!(a<b) && !(b<a)).

The elements in the range shall already besortedaccording to this same criterion (operator<orcomp), or at least partitionedwith respect toval.

范围内的容器应该是已经排序好了的，并且是使用相同的规则排序的（operator< or comp），至少排序到val。（即最后一个排序好的元素是val）.

例子：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void binary_s2(){

    vector<int> vi;
    vi.push_back(1);
    vi.push_back(3);
    vi.push_back(4);
    vi.push_back(7);
    vi.push_back(2);
    vi.push_back(5);
/*vi (1,3,4,7,2,5)*/



    if(binary_search(vi.begin(),vi.end(),1))
        cout<<"1 exits!"<<endl;
    else
        cout<<"1 didn't exits!"<<endl;


    if(binary_search(vi.begin(),vi.end(),7))
        cout<<"7 exits!"<<endl;
    else
        cout<<"7 didn't exits!"<<endl;

    if(binary_search(vi.begin(),vi.end(),2))
        cout<<"2 exits!"<<endl;
    else
        cout<<"2 didn't exits!"<<endl;


}

运行截图：

可以看到，7可以找到,但是2找不到！

The function optimizes the number of comparisons performed by comparing non-consecutive elements of the sorted range, which is specially efficient forrandom-access iterators.

该方法优化了比较不连续的元素的次数，随机访问迭代器则更为高效。

The behavior of this function template is equivalent to:

该函数的行为类似下面：

1 2 3 4 5 6

template <class ForwardIterator, class T> bool binary_search (ForwardIterator first, ForwardIterator last, const T& val) { first = std::lower_bound(first,last,val); return (first!=last && !(val<*first)); }

Parameters

first, last

Forward iteratorsto the initial and final positions of asorted(or properlypartitioned) sequence. The range used is[first,last), which contains all the elements betweenfirstandlast, including the element pointed byfirstbut not the element pointed bylast.
要排序序列的开头及结束位置，包括[first,last）里的所有元素，包括first,但不包括last指向的元素。

val

Value to search for in the range.
For(1),Tshall be a type supporting being compared with elements of the range[first,last)as either operand ofoperator<.
要查找的值。
对于（1），范围内的元素应该是已经排好序的。

comp

Binary function that accepts two arguments of the type pointed byForwardIterator(and of typeT), and returns a value convertible tobool. The value returned indicates whether the first argument is considered to go before the second.
The function shall not modify any of its arguments.
This can either be a function pointer or a function object.
接受两个参数兵返回一个bool值的二元函数，返回的值应该是看第一个元素是否在第二个元素之前。
该函数不应该修改参数。

Return value

trueif an element equivalent tovalis found, andfalseotherwise.
如果找到一个值和val相等，则返回true,否则返回false.

Example

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

// binary_search example #include <iostream> // std::cout #include <algorithm> // std::binary_search, std::sort #include <vector> // std::vector bool myfunction (int i,int j) { return (i<j); } int main () { int myints[] = {1,2,3,4,5,4,3,2,1}; std::vector<int> v(myints,myints+9); // 1 2 3 4 5 4 3 2 1 // using default comparison: std::sort (v.begin(), v.end()); std::cout << "looking for a 3... "; if (std::binary_search (v.begin(), v.end(), 3)) std::cout << "found!\n"; else std::cout << "not found.\n"; // using myfunction as comp: std::sort (v.begin(), v.end(), myfunction); std::cout << "looking for a 6... "; if (std::binary_search (v.begin(), v.end(), 6, myfunction)) std::cout << "found!\n"; else std::cout << "not found.\n"; return 0; }

Edit & Run

Output:

looking for a 3... found!
looking for a 6... not found.

Complexity

On average, logarithmic in thedistancebetweenfirstandlast: Performs approximatelylog2(N)+2element comparisons (whereNis this distance).

Onnon-random-accessiterators, the iteratoradvancesproduce themselves an additional linear complexity inNon average.

Data races

The objects in the range[first,last)are accessed.

Exceptions

Throws if either an element comparison or an operation on an iterator throws.

Note that invalid arguments causeundefined behavior.

——————————————————————————————————————————————————————————————————

//写的错误或者不好的地方请多多指导，可以在下面留言或者点击左上方邮件地址给我发邮件，指出我的错误以及不足，以便我修改，更好的分享给大家，谢谢。

转载请注明出处：http://blog.csdn.net/qq844352155

author:天下无双

Email:[e-mail]

2014-9-8

于GDUT

祝大家中秋节快乐！

——————————————————————————————————————————————————————————————————