std::binary_search() 算法

自 C++20 起

// (1)
template< class ForwardIt, class T >
constexpr bool binary_search( ForwardIt first, ForwardIt last, const T& value );

// (2)
template< class ForwardIt, class T, class Compare >
constexpr bool binary_search( ForwardIt first, ForwardIt last, const T& value, Compare comp );

直到 C++20

// (1)
template< class ForwardIt, class T >
bool binary_search( ForwardIt first, ForwardIt last, const T& value );

// (2)
template< class ForwardIt, class T, class Compare >
bool binary_search( ForwardIt first, ForwardIt last, const T& value, Compare comp );

检查一个等同于 `value` 的元素是否出现在范围 `[first; last)` 中。

要使 `std::binary_search` 成功，范围 `[first; last)` 必须至少相对于 `value` 部分有序，即它必须满足以下所有要求：

• 相对于 `element < value` 或 `comp(element, value)` 进行分区（即，所有使表达式为 `true` 的元素都先于所有使表达式为 `false` 的元素）
• 相对于 `!(value < element)` 或 `!comp(value, element)` 进行分区
• 对于所有元素，如果 `element < value` 或 `comp(element, value)` 为 `true`，则 `!(value < element)` 或 `!comp(value, element)` 也为 `true`

完全排序的范围满足这些标准。

• (1) 使用 `operator<` 比较元素。

• (2) 使用给定的比较函数 `comp` 比较元素。

参数

first last	要搜索的部分有序范围。
值	用于比较元素的 `value`。
comp	比较函数对象（即满足 Compare 要求的对象）。比较函数的签名应等同于以下内容： bool cmp(const Type1 &a, const Type2 &b); 签名不需要有 `const&`，但不得修改参数。 必须接受 `Type` 和 `Type2` 类型的所有（可能为 const）值，无论值类别如何（因此不允许 `Type1&`，也不允许 `Type1`，除非对于 `Type1`，移动等同于复制 （自 C++11 起）） `Type1` 和 `Type2` 类型必须是 `RandomIt` 类型的对象可以隐式转换为它们两者的类型。

类型要求

ForwardIt	LegacyForwardIterator
Compare	BinaryPredicate

`Compare` 不要求满足 Compare。

返回值

如果找到等于 `value` 的元素，则返回 `true`。

否则为 false。

复杂度

执行的比较次数与 `first` 和 `last` 之间的距离呈对数关系（最多 log2(last - first) + O(1) 次比较）。

然而，对于非 LegacyRandomAccessIterators，迭代器增量次数是线性的。

异常

(无)

可能的实现

binary_search (1)

template<class ForwardIt, class T>
bool binary_search(ForwardIt first, ForwardIt last, const T& value)
{
    first = std::lower_bound(first, last, value);
    return (!(first == last) and !(value < *first));
}

binary_search (2)

template<class ForwardIt, class T, class Compare>
bool binary_search(ForwardIt first, ForwardIt last, const T& value, Compare comp)
{
    first = std::lower_bound(first, last, value, comp);
    return (!(first == last) and !(comp(value, *first)));
}

示例

Main.cpp

#include <algorithm>
#include <iostream>
#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