时间戳

首页 > 解决方案 > 跳跃二分搜索有直观的解释吗？

c++ - 跳跃二分搜索有直观的解释吗？

问题描述

我正在阅读《竞技程序员手册》：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;

标签： c++arraysbinary-search

解决方案

书中的解释非常好！我将以它们为起点。

假设您有一本字典，您在第一页 ( 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- 字典包含 page 上的单词k，要么你的字典中没有这样的单词。

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

想象一下，您有一个数组，其中包含 in 的所有可能值!ok(i)（array[i]或 in 的所有可能值f(i) < f(i+1)）array[i]。然后你用array与 相同的方式进行二进制搜索array[k+b] <= x。

请注意，本书假定ok(i)并f(i)适用于 any i，而数组大小是有限的并且必须检查：k+b < n，n数组大小在哪里。

书中代码风格注意事项：

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

我明白这可能非常令人惊讶。在长期专业项目的世界中，为了实现速度而交易代码可读性是不可接受的。

推荐阅读