编程珠玑：专栏 9.3 二分查找——范围初始化
Programming Pearls: Column 9.3 Binary Search - range initialization
在作业 9.3 节中，Bentley 介绍了一种改进的二分搜索。
典型实现的简短片段和 9.3 中所示的更好方法
if (arr[mid] < key) low = mid+1
else if (arr[mid] > key) high = mid-1
else return mid;
modified/efficient 与不同不变量的比较..
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 ？有没有只有这行得通的极端情况？
如果您有一个空数组 (n == 0)，则 while(low + 1 != high) 的检查只有在 low 从 -1 和 high 在 0.
while((-1 + 1) != 0) //true
如果 low 开始于 0，或者 high 开始于 -1（或两者），那么循环显然会执行至少一项检查：
while((0 + 1) != 0) // falsewhile((-1 + 1) != -1) // falsewhile((0 + 1) != -1) // false
对空数组的检查可能会访问越界索引，这会调用未定义的行为。
在作业 9.3 节中，Bentley 介绍了一种改进的二分搜索。
典型实现的简短片段和 9.3 中所示的更好方法
if (arr[mid] < key) low = mid+1
else if (arr[mid] > key) high = mid-1
else return mid;
modified/efficient 与不同不变量的比较..
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 ？有没有只有这行得通的极端情况？
如果您有一个空数组 (n == 0)，则 while(low + 1 != high) 的检查只有在 low 从 -1 和 high 在 0.
while((-1 + 1) != 0) //true
如果 low 开始于 0，或者 high 开始于 -1（或两者），那么循环显然会执行至少一项检查：
while((0 + 1) != 0) // falsewhile((-1 + 1) != -1) // falsewhile((0 + 1) != -1) // false
对空数组的检查可能会访问越界索引，这会调用未定义的行为。