这种二进制搜索是否有名字？

Question

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

动机

首先，为了使搜索更容易理解，我将解释其催生创建使用情况。

假设您有一个有序号码列表。系统会要求您查找最接近x的列表中的编号索引。

int findIndexClosestTo(int x); 

的呼叫findIndexClosestTo()总是遵循这个规则：

如果findIndexClosestTo()最后的结果是i，然后指数接近i有幸成为当前呼叫的结果概率较大findIndexClosestTo()。

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

例如，想象一个在屏幕上左右走动的模拟男孩。如果我们经常查询男孩位置的指数，那么他可能就在我们找到他的最后一个地方。

算法

鉴于以上的情况下，我们所知道的findIndexClosestTo()最后的结果是i（这实际上是第一次函数被调用，i默认列表的中间指标，为简单起见，尽管单独的二进制搜索来查找第一个调用的结果实际上会更快），并且该函数已被再次调用。鉴于新号码x，我们按照这个算法来寻找其索引：

1. interval = 1;
2. 位于i我们正在寻找，x数？如果是这样，请返回i;
3. 如果不是，请确定x是高于还是低于i。 （请记住，清单是排序的。）
4. 移动interval指数的方向x。
5. 如果我们在新位置找到了x，请返回该位置。
6. Double interval。 （即interval *= 2）
7. 如果我们已经通过x，回去interval指标，设定interval = 1，进入4

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

Answer 1

你在做什么的（恕我直言）版本的Interpolation search

在插值搜索你承担数平均分配，那么你尝试从数组的第一个和最后一个数字和长度中猜测数字的位置。

对于您的情况，您正在修改interpolation-algo，以便您假定该键非常接近您搜索的最后一个数字。

另请注意，您的算法类似于算法TCP，它试图找到最优的数据包大小。 （不记得名字:(）

1. 开始缓慢
   1. 双区间
   2. 如果数据包无法重新从最后成功packet./从默认包大小。3重启 。

Answer 2

这是在谈论我的头顶，所以我没有任何支持它，但直觉！

在步骤7，如果我们已经通过X，它可能会更快减半interval了，头背对着x - 有效，interval = -(interval/2)，而不是重置interval为1

我得素描尽管...

编辑：道歉 - 我在上面说无稽之谈：不理我！ （并且我将离开并且有一个正确这次考虑它...）

Answer 3

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

假设你从0开始（有间隔= 1），并且你实际寻求值驻留在位置2^N - 1。

首先，将检查1，2，4，8，... ，2 ^（n-1），2^n。哎呀，那是超调，所以回到2 ^（n-1）。 （n-1）+1，2 ^（n-1）+2，...，2 ^（n-1）+ 2 ^（n-2），2 ^（（n-1）+2 ^（n-2） N-1）+ 2 ^（N-1）。最后一个词是2^n，所以哎哟，再一次超过。回到2 ^（n-1）+ 2 ^（n-2）。

依此类推，直到最后达到2 ^（N-1）+ 2 ^（N-2）+ ... + 1 == 2^N - 1.

第一过冲了日志n个步骤。接下来花了（log n）-1步。下一个花了（log n） - 2个步骤。等等。所以，最糟糕的情况是，你花了1 + 2 + 3 + ... + log n == O（（log n）^ 2）个步骤。

一个更好的主意，我认为是，当您第一次过调时切换到传统的二进制搜索。这将保持算法的O（log n）最差情况性能，而当目标确实在附近时，趋于更快一些。

我不知道这个算法的名字，但我喜欢它。 （通过一个奇怪的巧合，我能参加昨天用它，真的。）

Answer 4

你例程是典型的插值例程。如果用随机数（〜标准二分查找）调用它，则不会损失太多，但如果用缓慢增加的数字调用它，则不需要很长时间就可以找到正确的索引。

因此，这是一个合理的默认行为，用于搜索有序表格以进行插值。

这个方法在Numerical Recipes第3版第3.1节中有很长的讨论。