这个二进制搜索是如何工作的？

Question

我在一本书《做二进制搜索》中看到了这个方法，但无论我怎么尝试，我都无法理解它是如何工作的。有人能确切地向我解释一下它是如何工作的吗？

这本书的解释无助于：

这个想法是在我们靠近目标元素时跳跃并减慢速度。变量k和b包含数组中的位置和跳跃长度。如果数组包含元素x，搜索后x的位置将在变量k中。该算法的时间复杂度为O（log n），这是因为对每个跳转长度而言，同时循环中的代码最多执行两次。

我不明白的是k是如何在数组中迭代的？我们如何确保它不会跳过目标的索引？我尝试用示例值跟踪这个程序的一些运行，但无法找出k遵循的模式，以确定目标x是否存在于数组中。

int k = 1;
for (int b = n/2; b >= 1; b /= 2) {
while (k+b <= n && t[k+b] <= x) k += b;
}
if (t[k] == x) {} // x was found at index k

注意：我很清楚“通用二进制搜索算法”（使用开始、中间和结束索引的算法）

Answer 1

b是当前位置的跳跃长度。如您所见，b从n/2开始，每一步都被2除，直到达到1为止。

现在，对于每个b，记住b在for循环中的每一步都被2除以，我们运行一个time循环，在这个循环中我们将b添加到我们的当前位置，也就是k>。我们将b添加到k检查中，以获得两个条件：k b小于n（以确保我们不会出界），并且t[k b]小于而不是我们正在搜索的x。

这实际上意味着，对于每个b，我们将b添加到k中，直到它超过我们正在寻找的值为止。此时，while循环中断，我们除以b以更慢的速度接近目标，希望我们不会越过它。

最后的b只有一个，以确保我们不会错过x，如果它只是k位置后的下一个元素。

这样看，一辆车正朝着一个目标狂奔。起初，汽车以最大速度行驶，当它接近目标时，它会逐渐减速，直到到达目标。

与传统的二进制搜索的不同之处在于，在传统的二进制搜索中，我们遍历目标，然后回来，一遍又一遍，在每次迭代中，我们减少来回的步骤。在这个算法中，我们只前进（从不超过目标），但是我们通过除以b来不断减少步骤的长度。