bool binary_search(ForwardItarator beg, ForwardItarator end, const T& value);
bool binary_search(ForwardItarator beg, ForwardItarator end, const T& value,BinaryPredicate op);
对于二分查找有两种方式来调用,不过第二种不常用。当我们要获得被搜寻元素的位置时,应该使用lower_bound(),upper_bound(),equal_range()。为什么二分查找效率更高?主要就是因为,他是对数复杂度。最后的执行次数是Log型的。而有一点你不知道的是,当我们调用这个算法函数时,如果搭配的不是随机存取迭代器,那就就是线性复杂度,反之就是对数复杂度。什么是随机存取迭代器?STL中的vecotr::itator就是随机迭代器,它可以用[]来取vector中任意一个元素。list::itator就不是随即迭代器,因为它不能用[]来取list中的元素。而deque等容器配接的迭代器也是随机存取迭代器。下面,我们来实际操作一个二分查找:
#include "iostream"
#include "string"
#include "algorithm"
#include "vector"
#include "string"
#include "iterator"
using namespace std;
int main()
{
/*vector<int> IntVec;
istream_iterator<int> in(cin);
istream_iterator<int> eof;
copy(in,eof,back_inserter(IntVec));
if (binary_search(IntVec.begin(),IntVec.end(),6))
{
cout<<"找到了!"<<endl;
}
else
{
cout<<"没有找到!"<<endl;
}*/
vector<string> Intstr;
copy(istream_iterator<string>(cin),istream_iterator<string>(),back_inserter(Intstr));
if (binary_search(Intstr.begin(),Intstr.end(),"hello"))
{
cout<<"找到了!"<<endl;
}
else
{
cout<<"没有找到!"<<endl;
}
system("pause");
return 0;
}