C++

参考

<algorithm>

function template
<algorithm>

std::binary_search

默认 (1)
template <class ForwardIterator, class T>  bool binary_search (ForwardIterator first, ForwardIterator last,                      const T& val);
自定义 (2)
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 被认为是等价的，如果 (!(a<b) && !(b<a)) 或 (!comp(a,b) && !comp(b,a)) 。

范围内的元素应已根据相同的标准（operator< 或 comp）排序，或至少相对于 val 分区。

该函数通过比较已排序范围中的非连续元素来优化比较次数，这对于随机访问迭代器特别高效。

此函数模板的行为等同于
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));
}

参数

first, last
Forward iterators 指向已排序（或正确分区）序列的起始和结束位置。使用的范围是 [first,last)，它包含 first 和 last 之间的所有元素，包括 first 指向的元素，但不包括 last 指向的元素。
val
要在范围内搜索的值。
对于 (1)，T 应为支持与范围 [first,last) 的元素作为 operator< 的任一操作数进行比较的类型。
comp
二进制函数，它接受由 ForwardIterator 指向的类型的两个参数（以及 T 类型），并返回可转换为 bool 的值。返回值指示第一个参数是否被认为排在第二个之前。
该函数不得修改其任何参数。
这可以是函数指针或函数对象。

返回值

如果找到等价于 val 的元素，则返回 true，否则返回 false。

示例

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;
}

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


复杂度

平均而言，与 first 和 last 之间的距离成对数关系：执行大约 log2(N)+2 次元素比较（其中 N 是该距离）。
对于非随机访问迭代器，迭代器前进本身会在平均情况下产生额外的线性复杂度。

数据竞争

访问范围 [first,last) 中的对象。

异常

如果元素比较或迭代器操作引发异常，则抛出。
请注意，无效参数会导致未定义行为。

另见

find
在范围中查找值 （函数模板）
lower_bound
返回指向下界的迭代器 （函数模板）
upper_bound
返回指向上界的迭代器 （函数模板）
equal_range
获取相等元素的子范围 （函数模板）