在今天编写一些代码时，我发生了一种情况，这种情况导致我编写了一种我以前从未见过的二进制搜索 . 这个二进制搜索是否有名称，它真的是一个“二进制”搜索吗？
动机
首先，为了使搜索更容易理解，我将解释产生其创建的用例 .
假设您有一个有序号码列表 . 系统会要求您在列表中找到最接近x的数字索引 .
int findIndexClosestTo(int x);
对 findIndexClosestTo() 的调用始终遵循以下规则：
如果findIndexClosestTo（）的最后一个结果是i，则接近i的索引更有可能成为当前调用findIndexClosestTo（）的结果 .
换句话说，我们需要找到的索引更接近于我们找到的最后一个索引而不是它 .
举个例子，想象一个在屏幕上左右走动的模拟男孩 . 如果我们经常查询男孩所在地的指数，那么很可能他就在我们找到他的最后一个地方附近 .
算法
鉴于上述情况，我们知道 findIndexClosestTo() 的最后一个结果是 i （如果这实际上是第一次调用该函数， i 默认为列表的中间索引，为简单起见，尽管单独的二进制搜索找到结果第一次调用实际上会更快），并且再次调用该函数 . 给定新数字 x ，我们按照此算法查找其索引：
-
interval = 1; -
我们正在寻找的号码是
x，位于i？如果是这样，请返回i; -
如果不是，请确定
x是高于还是低于i. （请记住，列表已排序 . ） -
向
x方向移动interval个索引 . -
如果我们在新位置找到
x，请返回该位置 . -
双
interval. （即interval *= 2） -
如果我们已经通过
x，请返回intervalindices，设置interval = 1，转到4 .
鉴于上述概率规则（在Motivation Headers 下），我认为这是找到正确索引的最有效方法 . 你知道更快的方法吗？
4 回答
你在做什么是（恕我直言）Interpolation search的一个版本
在插值搜索中，您假设数字是均匀分布的，然后您尝试从数组的第一个和最后一个数字和长度猜测数字的位置 .
在您的情况下，您正在修改插值算法，以便假设Key非常接近您搜索的最后一个数字 .
另请注意，您的算法类似于算法，TCP试图找到最佳数据包大小 . （不记得名字:(）
开始慢
双倍间隔
如果数据包从最后一个成功的数据包重新启动失败./从默认数据包大小重启.3 .
在最坏的情况下，您的算法是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）最坏情况性能，而当目标确实在附近时趋向于更快 .
我不知道这个算法的名称，但我确实喜欢它 . （奇怪的巧合，我昨天可以用它 . 真的 . ）
您的例程是典型的插值例程 . 如果用随机数字（〜标准二进制搜索）调用它，你不会失去太多，但如果你用慢慢增加的数字来调用它，那么找到正确的索引就不会花费很长时间 .
因此，这是用于搜索有序表以进行插值的合理默认行为 .
在Numerical Recipes 3rd edition，3.1节中详细讨论了这种方法 .
这是我的头脑，所以我没有任何支持，但直觉！
在步骤7，如果我们已经通过了x，那么将
interval减半可能会更快，并且回到x- 实际上是interval = -(interval / 2)，而不是将interval重置为1 .我不得不在纸上勾勒出一些数字，不过......
编辑：道歉 - 我'm talking nonsense above: ignore me! (And I'这次会离开并正确地考虑一下...）