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

小编典典

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

algorithm

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

（附带说明，标准委员会在为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。

阅读 258

2020-07-28

共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)将迭代器返回给定项目的方法。但是，您的要求可能与集合的使用不兼容（例如，如果您需要多次存储同一元素）。

2020-07-28