C++ algorithm值binary_search

函数原型:

默认形式:
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)

上一篇:Latex 算法过长 分页显示方法


下一篇:java RA5 加密解密