binary search 中止条件 | Lxming's Weblog

binary search 中止条件 | Lxming's Weblog

binary search 中止条件

Binary search问题通常包含三个指针：lower， upper, mid. mid = (lower+upper)/2. 在每个循环调整upper/lower, 例如：

while(lower<=upper) {
mid = (lower+upper)/2;
if condition 1: lower=m+1;
if condition 2: upper = m-1;
}


但这个问题有很多变种，例如查找元素，查找Insert location, 有时候需要做lower=m, upper=m, 在这种情况下，如何保证loop能结束？

我终结了三种情况：
1）lower <= upper, lower=m+1, upper=m-1, 因为每次lower/upper都会改变，所以一定能结束。
2）lower <upper, lower=m+1, upper=m, 会结束循环。
3）lower <upper, m=(lower+upper+1)/2, lower=m, upper=m, 会结束循环。

以下情况不能结束：
4）lower <＝upper, lower=m+1, upper=m. 在这种情况下，如果upper=＝lower， mid也会变成lower,下一步upper还是lower, 所以是dead loop.
5) lower < upper, lower=m, upper=m-1. 在这种情况下，程序可能进入死循环。

一般问题的思考方式是在边界条件下（upper==lower, upper==lower+1), 循环是否能够结束。

Read full article from binary search 中止条件 | Lxming's Weblog