c++ - C++ std::binary_search() 和 std::lower_bound() 组合是否意味着我要进行两次二进制搜索？

Question

在我使用二进制搜索在 vector 中快速查找元素的搜索中，我找到了 std::binary_search 函数，但后来意识到它只返回一个 bool 值，这让我很沮丧。

但后来我发现以这种方式查找元素的最常见解决方案是将 binary_search() 与 lower_bound() 配对。仔细观察后，我认为 lower_bound() 也使用二进制搜索式的情况搜索元素。那么，这是否意味着我正在搜索它两次？

这是我所指的示例: std::vector haystack{ 1, 3, 4, 5, 9 }; int 针 = 5;

if (std::binary_search(haystack.begin(), haystack.end(), needle)) {
    std::cout << "Found " << needle << '\n';

    std::vector<int>::iterator it = lower_bound(haystack.begin(), haystack.end(), needle);

    int result = *it;

    cout << "Result " << result << endl;
}

我是不是做错了？有没有另一种方法可以对 vector 中的某些内容进行二进制搜索并获取实际找到的元素？

Answer 1

是的，您正在进行两次二进制搜索。只需使用一次 lower_bound 进行额外比较:

auto it = std::lower_bound(haystack.begin(), haystack.end(), needle);
if (it != haystack.end() && *it == needle) {
    // found it, here.
}

但只有在需要迭代器时才这样做。如果您只想检查 needle 是否存在，我会使用 std::binary_search() 来为您的用户增加清晰度。这可以很好地根据 lower_bound 开始实现。来自 cppreference :

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));
}