带提示的二分查找

我有一个简单的std::vector包含一些已排序的数字（按升序）。我想查找一个元素，到目前为止我使用：

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

Where needle是我寻找的元素。然而，我的向量往往很长（数百万个元素），但大多数时候内容是相对可预测的，从某种意义上说，如果第一个元素为零而最后一个元素是N，那么中间的元素的值接近(N * index) / vec.size()因此是可预测的。

是否有对下限的修改，它会接受提示（类似于如何std::map::emplace_hint() http://www.cplusplus.com/reference/map/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中实现的吗？

我认为您正在寻找的算法称为插值搜索 https://en.wikipedia.org/wiki/Interpolation_search这是二分搜索的一种变体，它不是查看数组的中点，而是在数组端点之间进行线性插值以猜测键应该在哪里。对于按照您的方式构建的数据，预期运行时间为 O(log log n)，比标准二分搜索快指数倍。

这个算法在 C++ 中没有标准实现，但是（作为一个完全无耻的插件）我碰巧用 C++ 编写了这个算法。我的实现可以在线获取 http://www.keithschwarz.com/interesting/code/?dir=interpolation-search如果您有兴趣了解它是如何工作的。

希望这可以帮助！