std::binary_search/std::lower_bound哪个函数效率高

在大多数情况下，`std::lower_bound`的效率更高，因为它可以在已排序的容器中进行快速查找，而不需要遍历整个容器。`std::binary_search`是用来判断一个元素是否存在于已排序的容器中，因此需要在整个容器中进行遍历，效率相对较低。

具体效率还要根据具体的使用情况来确定。如果需要多次查找同一个元素，那么使用`std::lower_bound`更加高效，因为它只需要一次定位，而`std::binary_search`需要多次遍历整个容器。

相关问题

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::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`是用于计算两个迭代器之间的距离。这个代码是标准库中的实现，实际上底层实现可能会有所不同，但是都是基于二分查找算法的思想。