algorithm - Programming Pearls, 2nd Edition 中关于二分查找的问题

Question

我正在阅读 Jon Bentley 的 Programming Pearls，第 2 版的第 9.3 节。

在第 94 页，Jon 给出了改进的二进制搜索算法的实现，利用 n 为 1000 的事实(搜索 1000 个数字以找到目标)。

程序结束时，是:

if p > 1000 || x[p] != t
    p = -1

我的问题是，如果 p 正好是 1000 怎么办？似乎当 p 为 1000 时，它也应该会出错，例如:

if p >= 1000 || x[p] != t
    p = -1

无论如何，这部分代码是从第93页的代码翻译过来的，最后:

if p >= n || x[p] != t
    p = -1

我的理解对吗？我只是想知道这是不是打错了，或者真的没有必要在条件中包含 p 是 1000 的情况。

另一个问题是，第94页从下往上的第5~6行说:当第一个测试失败并且l保持为零时，程序按顺序计算p的位，最高有效位在前。

这里是什么意思？当第一个测试失败时，l 不应该是 -1，而不是 0？

任何人都可以详细说明这个声明吗？

附言我找不到 Jon 的电子邮件地址，否则，我会向他提出这些问题。 :-(

Answer 1

错别字。 l 的最大值是 999 (1000 - 512 + 256 + .. + 1, )，所以 p = l+1 的最大值是 1000。对于 binsearch 的硬编码版本( list 9.8)来说很明显。

而且我们可以看到真正的 C 代码(不是伪代码)here (Alg.4)与 if (p >= n ||