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

Question

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

在第 32 页及以上(PDF 第 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)。

不变的假设是:

1. 词典中的单词是非降序排列的(对于每个 i , 0 < i < n : array[i-1] <= array[i] )，
2. 您当前正在查看 的字词 ( array[k] ) 永远不会大于您正在寻找的 字词 ( array[k] <= 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 的基本相同.

假设您有一个包含所有可能值 !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 。