二分查找

类别: 算法	组件类型: 函数

原型

template <class ForwardIterator, class LessThanComparable>
bool binary_search(ForwardIterator first, ForwardIterator last,
                   const LessThanComparable& value);

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

说明

具体而言，第一个版本返回当有一个元素与 [1] 相等时当且仅当存在一个迭代器i在它返回中，使得*i < value返回value < *i都是false。第二个版本返回当有一个元素与 [1] 相等时当且仅当存在一个迭代器i在它返回中，使得comp(*i, value)返回comp(value, *i)都是false.

定义

对类型的要求

• ForwardIterator是 向前迭代器 的模型。
• LessThanComparable是 小于可比较类型 的模型。
• 类型LessThanComparable上的排序是一个严格的弱排序，如 小于可比较类型 的要求中所定义的。
• ForwardIterator的值类型与类型相同LessThanComparable.

• ForwardIterator是 向前迭代器 的模型。
• StrictWeakOrdering是 严格的弱排序 的模型。
• ForwardIterator的值类型与类型相同T.
• ForwardIterator的值类型可转换为StrictWeakOrdering的参数类型。

前提条件

• 它返回是一个有效的范围。
• 它返回根据operator<以升序排列。也就是说，对于每一对迭代器i返回j在它返回中，使得i先于j, *j < *i是false.

• 它返回是一个有效的范围。
• 它返回根据 函数对象comp以升序排列。也就是说，对于每一对迭代器i返回j在它返回中，使得i先于j, comp(*j, *i)是false.

以升序排列。

last - first

int main()
{
  int A[] = { 1, 2, 3, 3, 3, 5, 8 };
  const int N = sizeof(A) / sizeof(int);

  for (int i = 1; i <= 10; ++i) {
    cout << "Searching for " << i << ": "
         << (binary_search(A, A + N, i) ? "present" : "not present") << endl;
  }
}

Searching for 1: present
Searching for 2: present
Searching for 3: present
Searching for 4: not present
Searching for 5: present
Searching for 6: not present
Searching for 7: not present
Searching for 8: present
Searching for 9: not present
Searching for 10: not present

示例

输出是注释返回[1] 请注意，您可以使用一种严格弱排序，但不是总排序；也就是说，可能有一些值中，使得x, yx < yx > y，并且falsex == y值范围内它返回时，并不意味着找到一个等于值而是找到一个等同于值：既不比...大也不比...小值。但是，如果你使用的是一个全序（比如你使用strcmp，比如，或者如果你对整数使用普通的算术比较），那么你就可以忽略这种技术上的区别：对于全序，相等和等同是相同的。

[2] 请注意，这并不一定是你感兴趣的信息！通常，如果你正在测试一个元素是否出现在一个范围内，你会想知道它在哪里（如果它存在）或者它应该插入在哪里（如果它不存在）。这些函数下界, 上界x < y等值范围提供此信息。

[3] 随机访问迭代器 和 前向迭代器 之间的这种差异仅仅是因为advance对于 随机访问迭代器 是恒定时间，而对于 前向迭代器 是线性时间。

另请参见