std::binary_search

Defined in header <algorithm>
template< class ForwardIt, class T > bool binary_search( ForwardIt first, ForwardIt last, const T& value );	(1)
template< class ForwardIt, class T, class Compare > bool binary_search( ForwardIt first, ForwardIt last, const T& value, Compare comp );	(2)

检查是否有等效于value出现在范围内[first, last)...

为std::binary_search要想成功，范围[first, last)必须至少部分排序，即必须满足下列所有要求：

的分区element < value或comp(element, value)

的分区!(value < element)或!comp(value, element)

对于所有元素，如果element < value或comp(element, value)是true然后!(value < element)或!comp(value, element)也是true

完全排序的范围符合这些条件，调用std::partition...

第一个版本使用operator<为了比较元素，第二个版本使用给定的比较函数。comp...

参数

first, last	-	the range of elements to examine
value	-	value to compare the elements to
comp	-	comparison function object (i.e. an object that satisfies the requirements of Compare) which returns true if the first argument is less than (i.e. is ordered before) the second. The signature of the comparison function should be equivalent to the following: bool cmp(const Type1 &a, const Type2 &b); The signature does not need to have const &, but the function object must not modify the objects passed to it. The types Type1 and Type2 must be such that an object of type T can be implicitly converted to both Type1 and Type2, and an object of type ForwardIt can be dereferenced and then implicitly converted to both Type1 and Type2.

类型要求

---。

返回值

true如果元素等于value被发现了，false否则。

复杂性

执行的比较数为对数，其距离为first和last%28%，大部分原木

2%28最后-首%29+O%281%29比较%29。但是，对于非-RandomAccessIterator斯，迭代器增量的数目是线性的。

可能的实施

第一版

*。

模板<类向前，类T>bool二进制[医]搜索%28 Forwardit First，Forwardit Lest，Const T&value%29{first=std：：lower[医]绑定%281，最后，值%29；返回%28%21%281==最后%29&%21%28值<%2A第一%29%29；}

第二版

模板<类向前，类T，类比较>bool二进制[医]搜索%28 Forwardit First，Forwardit Lest，Const T&Value，比较comp%29{first=std：：lower[医]绑定%281，最后，值，comp%29；返回%28%21%281==最后%29&%21%28 comp%28值，%2A第一%29%29%29；}

例

二次

#include <iostream>
#include <algorithm>
#include <vector>
 
int main()
{
    std::vector<int> haystack {1, 3, 4, 5, 9};
    std::vector<int> needles {1, 2, 3};
 
    for (auto needle : needles) {
        std::cout << "Searching for " << needle << '\n';
        if (std::binary_search(haystack.begin(), haystack.end(), needle)) {
            std::cout << "Found " << needle << '\n';
        } else {
            std::cout << "no dice!\n";
        }
    }
}

二次

产出：

二次

Searching for 1
Found 1
Searching for 2
no dice!
Searching for 3
Found 3

二次

另见

equal_range	returns range of elements matching a specific key (function template)

 © cppreference.com

在CreativeCommonsAttribution下授权-ShareAlike未移植许可v3.0。

http：//en.cppreference.com/w/cpp/Algorithm/二进制[医]搜索

本文档系腾讯云开发者社区成员共同维护，如有问题请联系 cloudcommunity@tencent.com

最后更新于：2017-12-18