二进制搜索提示

Question

我有一个简单的std::vector包含一些数字,这些数字是按升序排序的.我想查找一个元素,到目前为止我使用:

return std::lower_bound(vec.begin(), vec.end(), needle);

needle我寻找的元素在哪里.然而,我的向量往往很长(数百万个元素),但大多数时候内容是相对可预测的,如果第一个元素是零而最后一个元素是N,那么其间的元素值接近于(N * index) / vec.size()因此是可预测的.

是否有下限的修改,它会接受提示(类似于如何std::map::emplace_hint()),例如:

assert(!vec.empty());
std::vector<int>::iterator hint = vec.begin() + std::min(vec.size() - 1,
    (needle * vec.size()) / vec.back());
if(*hint > needle)
    return std::lower_bound(vec.begin(), hint, needle);
else
    return std::lower_bound(hint, vec.end(), needle);

这将起作用,但是lower_bound忽略它接近解决方案并且很可能开始将间隔分成两半(看看我们知道针最有可能不在哪里),采取不必要的许多步骤.我知道有一个算法从步骤1开始,它加倍,直到它超过针,然后在给定的间隔内进行二元搜索.

我忘了算法的名称是什么.它是在STL中实现的吗？

Answer 1

我认为您正在寻找的算法称为插值搜索,它是二进制搜索的一种变体,它不是查看数组的中点,而是在数组端点之间进行线性插值,以猜测密钥的位置.对于按照您的方式构建的数据,预期的运行时为O(log log n),比标准二进制搜索指数级快.

在C++中没有这个算法的标准实现,但是(作为一个完全无耻的插件)我碰巧用C++编写了这个.如果您有兴趣了解它的工作原理,我的在线实施.

希望这可以帮助!