函数原型:
默认形式:
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);
作用:
在范围[first, last)内有元素等于val将返回true,否则返回false。元素比较对于第一个版本使用的是operator<,第二个版本使用comp。
以下情况我们认为a和b相等if(!(a<b) && !(a>b))或if(!comp(a,b) && !comp(b,a))。
该范围内的元素应该根据相同的标准(operator< 或 camp)进行排序,或者至少应该针对val分区。
该功能通过比较排序范围内的非连续元素来优化比较次数,这对于随机访问迭代器特别有效。
模板函数的行为等价于如下代码:
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)); }
参数:
first,last:
前向迭代器指向一个排序(或合适分块)序列的初始位置和结束位置。序列的范围[first,last),包括first至last的所有元素,
包括first指向的元素,但是不包括last指向的元素。
val:
在范围内查找的值。对于默认的函数形式,该范围内的类型需支持元素比较(即支持operator<)。
comp:
二元函数接受两个前向迭代器指向的参数,并返回一个可以转换为bool的值。返回值确定了是否要把第一个参数排在第二个
参数前。该函数不应该修改他的参数。这项可以是函数指针或函数对象。
返回值:
如果有元素等于val,则返回true,否则返回false。
例子:
// 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; }
Output:
looking for a 3... found! looking for a 6... not found.
时间复杂度:
log2(N)