algorithm - 这种类型的二进制搜索有名称吗？

Question

今天在写一些代码时，我遇到了一种情况，导致我编写了一种我以前从未见过的二进制搜索。这个二分搜索有名字吗，它真的是“二分”搜索吗？

动机

首先，为了使搜索更容易理解，我将解释产生它的创建的用例。

假设您有一个有序数字列表。要求您在列表中找到最接近 x 的数字的索引。

int findIndexClosestTo(int x);

findIndexClosestTo() 的调用总是遵循以下规则:

If the last result of findIndexClosestTo() was i, then indices closer to i have greater probability of being the result of the current call to findIndexClosestTo().

换句话说，我们这次需要找到的索引更有可能更接近我们找到的最后一个而不是更远。

举个例子，想象一个模拟男孩在屏幕上左右走动。如果我们经常查询男孩位置的索引，他很可能就在我们最后一次找到他的地方附近。

算法

鉴于上述情况，我们知道 findIndexClosestTo() 的最后结果是 i(如果这实际上是函数第一次被调用， i 默认为列表的中间索引，为简单起见，尽管单独的二进制搜索来查找第一次调用的结果实际上会更快)，并且该函数已被再次调用。给定新数字 x，我们按照以下算法找到它的索引:

1. 间隔 = 1;
2. 我们要查找的数字x 是否位于i？如果是，返回i;
3. 如果不是，则确定x 是高于还是低于i。 (请记住，列表已排序。)
4. 在 x 方向移动 interval 索引。
5. 如果我们在新位置找到了x，返回那个位置。
6. 双间隔。 (即 interval *= 2)
7. 如果我们已经通过 x，返回 interval 索引，设置 interval = 1，转到 4。

鉴于上述概率规则(在动机标题下)，在我看来，这是找到正确索引的最有效方法。你知道更快的方法吗？

Answer 1

在最坏的情况下，您的算法是 O((log n)^2)。

假设您从 0 开始(间隔 = 1)，并且您寻找的值实际上位于位置 2^n - 1。

首先您将检查 1, 2, 4, 8, ..., 2^(n-1), 2^n。糟糕，超调了，所以回到 2^(n-1)。

接下来检查 2^(n-1)+1, 2^(n-1)+2, ..., 2^(n-1)+2^(n-2), 2^(n -1)+2^(n-1)。最后一项是 2^n，哎呀，又超过了。回到 2^(n-1) + 2^(n-2)。

依此类推，直到最终达到 2^(n-1) + 2^(n-2) + ... + 1 == 2^n - 1。

第一次超调采取了 log n 步。接下来采取了 (log n)-1 步。接下来采取了 (log n) - 2 个步骤。等等。

所以，最坏的情况下，您需要 1 + 2 + 3 + ... + log n == O((log n)^2) 步。

我认为，一个更好的主意是，一旦您第一次超出范围，就切换到传统的二进制搜索。这将保留算法的 O(log n) 最坏情况性能，同时当目标确实在附近时往往会更快一些。

我不知道这个算法的名字，但我确实喜欢它。 (巧合的是，我昨天就可以使用它。真的。)