algorithm - 编程 Pearls : Column 9. 3 二分查找 - 范围初始化

Question

在第 9.3 节中，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;

在循环之外，会检查键是否位于索引“high”。在修改后的二分搜索中，左索引“low”从 -1(而不是 0)开始，“high”索引从 n(而不是 n-1)开始。循环运行

while (low + 1 != high)

即使我设置 low = 0 和 high = n-1，此修改后的搜索似乎也能工作。

但我不想在他的代码中再次猜测 Job Bentley。那么为什么他将 low 设置为 -1 而将 high 设置为 n 呢？是否存在仅此方法有效的极端情况？

Answer 1

如果您有一个空数组 (n == 0)，则 while(low + 1 != high) 的检查仅在以下情况下才会正确终止: low 从 -1 开始，high 从 0 开始。

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

如果low从0开始，或者high从-1开始(或两者)，那么该循环显然将执行至少一项检查:

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

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