c++ - 跳转二进制搜索有直观的解释吗？

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

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

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
}

找到对函数正常的最小值

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;

最佳答案

书中的解释很好!我将以它们为起点。

假设您有一本词典，在第一页上打开它(int k = 0;)，然后在词典中寻找一个单词(x)。

不变的假设是:

字典中的

单词按非降序排列(对于每个i，0 <i <n:array[i-1] array[i])，

您当前在上查找的单词(array[k])永远不会比您在上查找的单词更大(array[k] x始终为真)。

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

只要您可以(即只要满足假设2)，就可以将当前位置k移到b的猜测页面数之前。然后您再次猜测，将猜测的距离b减半。

当b变为1时，您已经在想要的字典中找到该页面。要么array[k] == x-词典包含k页上的单词，要么词典中没有此类单词。

后面带有!ok(x+b)和f(x+b) < f(x+b+1)的示例与带有array[k+b] <= x的示例基本相同。

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

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

注意本书中的代码风格:

在竞争性编程中，您只有很有限的时间来解决大量算法问题，而不必再看代码，因此可以使用短变量名，不加注释等。通常也可以看到许多#DEFINE指令-例如参见https://gist.github.com/kodekracker/e09f9d23573f117a5db0。

我了解这可能会非常令人惊讶。在长期专业项目的世界中，要以如此高的速度读取代码以提高实现速度是 Not Acceptable 。

关于c++ - 跳转二进制搜索有直观的解释吗？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/56108263/