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
獲取相等元素的子範圍 （函式模板）