algorithm - 编程珍珠：第 9.3 列二分搜索 - 范围初始化

Question

在第 9.3 节中，Job Bentley 提出了一种修改后的二分搜索。

9.3 中显示的典型实现和更好方法的简短片段

if (arr[mid] < key) low = mid+1
else if (arr[mid] > key) high = mid-1
else return mid;

与不同不变量的修改/有效比较..

if (arr[mid] < key) low = m;
else high = m;

在循环之外，检查索引处的键是否为“高”。在修改后的二分搜索中，左索引“low”从-1（而不是0）开始，“high”索引从n（而不是n-1）开始......并且循环运行

while (low + 1 != high)

即使我设置低 = 0 和高 = n-1，这个修改后的搜索似乎也有效。

但我宁愿不要在他的代码中猜测 Job Bentley。那么他为什么将 low 设置为 -1 而 high 设置为 n 呢？是否有任何极端情况只能这样工作？

Answer 1

如果您有一个空数组 ( n == 0)，那么只有在开始于和at时，对while(low + 1 != high) 的检查才会正确终止。low-1high0

while((-1 + 1) != 0) //true

如果low开始于0，或high开始于-1（或两者），则循环将清楚地执行至少一项检查：

• while((0 + 1) != 0) // false
• while((-1 + 1) != -1) // false
• while((0 + 1) != -1) // false

对空数组的一次检查可能会访问越界索引，这会调用未定义的行为。