c++ - 我在哪里可以获得 "useful"C++ 二分搜索算法？

Question

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

(顺便说一句，标准委员会在为 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 .

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)到给定的项目。但是，您的要求可能与使用集合不兼容(例如，如果您需要多次存储同一个元素)。