std::binary_search/std::lower_bound

`std::binary_search`和`std::lower_bound`都是C++ STL中的搜索算法，用于在有序序列中查找特定元素。

`std::binary_search`函数接受三个参数：一个指向序列的起始位置的迭代器，一个指向序列的结束位置的迭代器以及要查找的值。该函数返回一个布尔值，指示序列中是否存在该值。如果存在，则返回`true`；否则，返回`false`。

`std::lower_bound`函数也接受三个参数：一个指向序列的起始位置的迭代器，一个指向序列的结束位置的迭代器以及要查找的值。该函数返回一个迭代器，指向序列中第一个不小于该值的元素。如果序列中所有元素都小于该值，则返回结束迭代器。

这两个函数的区别在于，`std::binary_search`只能确定是否存在该值，而`std::lower_bound`可以找到第一个不小于该值的元素。如果需要找到第一个大于该值的元素，可以使用`std::upper_bound`函数。

相关问题

std::lower_bound为什么比std::binary_search/std::lower_bound效率高

std::lower_bound 和 std::binary_search 都是 C++ STL 中的算法，用于在有序序列中查找某个元素。它们的目的不同，std::lower_bound 用于查找第一个大于等于给定值的元素的位置，而 std::binary_search 用于判断给定值是否在序列中出现过。

在实现上，std::lower_bound 采用了二分查找的思想，通过不断缩小查找区间的范围，最终找到目标值或者第一个大于等于目标值的位置。而 std::binary_search 也是采用了二分查找的思想，通过不断缩小查找区间的范围，最终判断目标值是否在序列中出现过。

因为 std::lower_bound 只需要找到第一个大于等于目标值的位置，而不需要判断目标值是否存在，所以它的实现比 std::binary_search 更加高效。此外，std::lower_bound 还可以通过返回值进行插入操作，可以说是一个非常实用的算法。

std::binary_search/std::lower_bound的底层实现

`std::binary_search`和`std::lower_bound`都是标准库中用于二分查找的算法。

`std::binary_search`用于判断一个元素是否在一个已排序的序列中存在，其底层实现通常是使用二分查找（也称折半查找）算法，即每次将查找范围折半，直到找到目标元素或者查找范围为空。

`std::lower_bound`用于查找一个已排序的序列中第一个不小于给定值的元素的位置，其底层实现也是使用二分查找算法，不同的是每次折半时，如果中间元素小于目标值，则将查找范围缩小到中间元素的右侧，否则缩小到中间元素的左侧。

具体实现可以参考以下代码：

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 && !(value < *first));
}

template<class ForwardIt, class T>
ForwardIt lower_bound(ForwardIt first, ForwardIt last, const T& value)
{
    while (first != last) {
        ForwardIt mid = std::next(first, std::distance(first, last) / 2);
        if (value > *mid) {
            first = std::next(mid);
        } else {
            last = mid;
        }
    }
    return first;
}

其中`std::next`是C++ STL中的函数，用于得到指定迭代器的后继迭代器，`std::distance`是用于计算两个迭代器之间的距离。这个代码是标准库中的实现，实际上底层实现可能会有所不同，但是都是基于二分查找算法的思想。