跳转二分查找有直观的解释吗？

Question

我正在阅读竞争性程序员手册：https://cses.fi/book/book.pdf

在第 32 页及以上 (PDF pp 42) 中，提到了二进制搜索的方法 2，我不确定我是否完全理解它。然后他们稍微修改它以找到最小值，使得函数 ok() 为真，并尝试在数组中找到最大值。我不直观地理解这里发生了什么。有什么直观的解释吗？

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

找到适用于函数 ok 的最小值

int x = -1;
for (int b = z; b >= 1; b /= 2) {
    while (!ok(x+b)) x += b;
}
int k = x+1;

求先增后减函数的最大值

int x = -1;
for (int b = z; b >= 1; b /= 2) {
    while (f(x+b) < f(x+b+1)) x += b;
}
int k = x+1;

Answer 1

书上讲解的很好！我将以它们为起点。

假设你有一本字典，你在第一页打开它 (int k = 0;)，你正在字典中查找一个词 (x)。

不变的假设是：

b 是您猜测距离您的答案还有多少页。在二进制搜索中，您总是猜测最大可能距离的一半。最初，可能的最大距离是字典的长度 n。所以最初，您将字典长度的一半作为您的猜测 - int b = n/2;.

您将当前位置 k 尽可能向前移动到猜测的页数 b，即只要满足假设 2。然后你再猜，把你猜的距离减半 b.

当 b 变为 1 时，您已经在字典中找到了您要查找的页面。 array[k] == x - 字典包含第 k 页上的单词，或者您的字典中没有这样的单词。

!ok(x+b)和f(x+b) < f(x+b+1)后面的例子与array[k+b] <= x的例子本质上是一样的。

假设您有一个数组，其中包含 array[i] 中 !ok(i) 的所有可能值（或 array[i] 中 f(i) < f(i+1) 的所有可能值）。然后你对 array 进行二进制搜索，方法与 array[k+b] <= x.

相同

请注意，本书假定 ok(i) 和 f(i) 适用于任何 i，而数组大小有限且必须检查：k+b < n，其中 n 是数组大小。

书中代码风格注意事项：

在竞争性编程中，您只有非常有限的时间来解决大量算法问题并且永远不会再看代码，可以使用短变量名、没有注释等。这也很常见看到许多 #DEFINE 指令 - 例如参见 [=44=] .

我明白这可能是多么令人惊讶。在 long-term 专业项目的世界里，以如此大的代价换取代码可读性是不可接受的。

Is there an intuitive explanation for the jumping binary search?