我在哪里可以获得“有用的”C 二进制搜索算法？

Question

我需要一个与 C++ STL 容器兼容的二进制搜索算法，例如标准库的 <algorithm> std::binary_search 头中的 —，但我需要它返回指向结果的迭代器，而不是一个简单的布尔值告诉我元素是否存在。

（顺便说一句，标准委员会在为 binary_search 定义 API 时到底在想什么？！）

我主要关心的是我需要二进制搜索的速度，所以虽然我可以使用其他算法找到数据，如下所述，但我想利用我的数据已排序的事实来获得二进制的好处搜索，而不是线性搜索。

到目前为止 lower_bound 和 upper_bound 如果缺少数据则失败：

 //lousy pseudo code
vector(1,2,3,4,6,7,8,9,0) //notice no 5
iter = lower_bound_or_upper_bound(start,end,5)
iter != 5 && iter !=end //not returning end as usual, instead it'll return 4 or 6

注意： 只要它与容器兼容，我也可以使用不属于 std 命名空间的算法。比如说， boost::binary_search 。

原文由 Robert Gould 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

没有这样的函数，但您可以使用 std::lower_bound 、 std::upper_bound 或 std::equal_range 编写一个简单的函数。

一个简单的实现可能是

template<class Iter, class T>
Iter binary_find(Iter begin, Iter end, T val)
{
    // Finds the lower bound in at most log(last - first) + 1 comparisons
    Iter i = std::lower_bound(begin, end, val);

    if (i != end && !(val < *i))
        return i; // found
    else
        return end; // not found
}

另一种解决方案是使用 std::set ，它保证元素的顺序并提供一种方法 iterator find(T key) 返回给定项目的迭代器。但是，您的要求可能与使用集合不兼容（例如，如果您需要多次存储相同的元素）。

原文由 Luc Touraille 发布，翻译遵循 CC BY-SA 3.0 许可协议

Answer 2

最短的实现，想知道为什么它没有包含在标准库中：

 template<class ForwardIt, class T, class Compare=std::less<>>
ForwardIt binary_find(ForwardIt first, ForwardIt last, const T& value, Compare comp={})
{
    // Note: BOTH type T and the type after ForwardIt is dereferenced
    // must be implicitly convertible to BOTH Type1 and Type2, used in Compare.
    // This is stricter than lower_bound requirement (see above)

    first = std::lower_bound(first, last, value, comp);
    return first != last && !comp(value, *first) ? first : last;
}

来自 https://en.cppreference.com/w/cpp/algorithm/lower_bound

原文由 trozen 发布，翻译遵循 CC BY-SA 4.0 许可协议