c++ - 带提示的二分搜索

Question

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

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

needle 是我要查找的元素。但是，我的 vector 往往很长(数百万个元素)，但大多数时候内容是相对可预测的，如果第一个元素为零并且最后一个元素是 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

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

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

希望这会有所帮助!