c++用标准库的功能实现binary_search

在C++中，`std::binary_search`是STL（Standard Template Library，标准模板库）的一部分，用于在一个已排序的容器内快速查找指定元素。基本用法如下[^1]：

#include <algorithm> // 包含binary_search头文件
#include <vector>    // 示例中使用vector

// 定义一个已排序的整数向量
std::vector<int> v = {1, 2, 3, 4, 5};

// 使用binary_search查找元素3
bool found = std::binary_search(v.begin(), v.end(), 3);

// 如果找到，打印"Found X!"
if (found)
{
    std::cout << "Found 3!" << std::endl;
}
else
{
    std::cout << "Did not find 3." << std::endl;
}

// 输出：Found 3!

这个函数的工作原理是从向量的一端开始比较，如果目标值小于当前元素，就移动到下一个较大的元素继续比较，直到找到等于或大于目标值的元素，或者遍历完整个序列。如果找到了目标值，函数返回`true`；否则返回`false`。

相关问题

std::binary_search

`std::binary_search` 是 C++ 标准库中的一个算法函数，用于在已排序的序列中查找指定的元素。它接收一个指向序列起始位置的迭代器 `first`，一个指向序列结束位置的迭代器 `last`，以及要查找的元素值 `value`。

使用该函数进行查找时，函数会通过比较序列中间元素和 `value` 的大小关系来判断 `value` 是否在序列中。如果序列中间元素等于 `value`，则查找成功，返回 `true`；否则，如果序列中间元素大于 `value`，则继续在序列左半部分查找；如果序列中间元素小于 `value`，则继续在序列右半部分查找。一直重复这个过程，直到找到 `value` 或者序列被遍历完为止。

如果查找成功，返回 `true`，否则返回 `false`。

示例代码：

#include <iostream>
#include <algorithm>
#include <vector>

int main() {
    std::vector<int> v {1, 4, 5, 7, 9, 10};
    int value = 5;

    bool result = std::binary_search(v.begin(), v.end(), value);

    if (result) {
        std::cout << "Value " << value << " is found!" << std::endl;
    } else {
        std::cout << "Value " << value << " is not found!" << std::endl;
    }

    return 0;
}

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