我在哪里可以得到一个“有用的"?C++二分查找算法?

问题描述

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

I need a binary search algorithm that is compatible with the C++ STL containers, something like std::binary_search in the standard library's <algorithm> header, but I need it to return the iterator that points at the result, not a simple boolean telling me if the element exists.

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

(On a side note, what the hell was the standard committee thinking when they defined the API for binary_search?!)

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

My main concern here is that I need the speed of a binary search, so although I can find the data with other algorithms, as mentioned below, I want to take advantage of the fact that my data is sorted to get the benefits of a binary search, not a linear search.

到目前为止 lower_bound 和 upper_bound 如果数据丢失则失败:

so far lower_bound and upper_bound fail if the datum is missing:

//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.

Note: I'm also fine using an algorithm that doesn't belong to the std namespace as long as its compatible with containers. Like, say, boost::binary_search.

推荐答案

没有这样的函数，但是你可以用 std::lower_bound, std::upper_bound 或 std::equal_range.

There is no such functions, but you can write a simple one using std::lower_bound, std::upper_bound or 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)到给定的项目.但是，您的要求可能与集合的使用不兼容(例如，如果您需要多次存储相同的元素).

Another solution would be to use a std::set, which guarantees the ordering of the elements and provides a method iterator find(T key) that returns an iterator to the given item. However, your requirements might not be compatible with the use of a set (for example if you need to store the same element multiple times).

这篇关于我在哪里可以得到一个“有用的"?C++二分查找算法?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持跟版网！