二分查找中的死循环

二分算法是我们经常会用到的一个算法。它是分治法的一个应用。不过，虽然他写起来貌似很简单，但是却很容易写错。下面我们讨论一下二分的死循环问题。（这里讨论的是整数的二分问题，浮点数的二分不容易死循环）1.查找的元素确定，值唯一或者不存在这种情况等下，我们的流程分为三个分支：（相等、小于、大于）。这类不容易死循环，代码如下：if （ data[mid] == key ）
return mid;
if （ data[mid] > key ）
r = mid-1;
else l = mid+1;2.被查元素不确定，值可能有多个，找到第一个或者最后一个这是最容易出现死循环的情况，也是本文讨论的核心。这种情况下，流程分成两个分支，我们分两种情况讨论：a.取第一个小于key的元素：if （ data[mid] >= key ）
r = mid-1;
else l = mid;我们看式子 mid = （l+r）/2如果（l+r）为奇数，则mid = （l+r）/2 = （l+r-1）/2 导出 2*mid = （l+r-1）/2*2 = l+r-1这时，若 mid = l 则“else l = mid;”这句代码就会就会进入死循环。所以这时使用 mid = （l+r+1）/2 代替 mid = （l+r+1）/2 就不会死循环了。如果（l+r+1）为偶数，则mid = （l+r+1）/2 = （l+r）/2 导出 2*mid = （l+r）/2*2 = l+r 不会出现问题。（这时使用 mid = （l+r）/2 也不会死循环）综上，这种情况下使用 mid = （l+r+1）/2 就不会死循环了，不过这不是通用式子，看b情况。int bs（ int l, int r, int key ）
{
while （ l < r ） {
int mid = （l+r+1）/2;
if （ data[mid] >= key ）
r = mid-1;
else l = mid;
}
return l;
}b.取第一个大于key的元素：if （ data[mid] <= key ）
l = mid+1;
else r = mid;我们看式子 mid = （l+r+1）/2如果（l+r+1）为奇数，则mid = （l+r+1）/2 = 导出 2*mid = （l+r+1）/2*2 = l+r+1这时，若 mid = r 则“else r = mid;”这句代码就会就会进入死循环。所以这时要使用 mid = （l+r）/2 代替 mid = （l+r+1）/2 才不会死循环了。如果（l+r）为偶数，则mid = （l+r）/2 导出 2*mid = （l+r）/2*2 = l+r不会出现问题。（这时使用 mid = （l+r+1）/2 也不会死循环）综上，这种情况下使用 mid = （l+r）/2 就不会死循环了。int bs（ int l, int r, int key ）
{
while （ l < r ） {
int mid = （l+r）/2;
if （ data[mid] <= key ）
l = mid+1;
else r = mid;
}
return r;
}c.综合a、b得到结论取中值的计算方式与判断条件有关，下面加入一个小优化。3.一步小优化，防止溢出这里使用 mid = l+（r-l）/2 代替 mid = （l+r）/2 以及 mid = l+（r-l+1）/2 代替 mid = （l+r+1）/2。这样可以防止l+r和l+r+1溢出。下面证明两者的等价性。a.l+r为奇数，则r-l为奇数,r-l+1为偶数mid = l+（r-l+1）/2 = l*2/2 + （r-l+1）/2 = （l+r+1）/2mid = l+（r-l）/2 = l*2/2 + （r-l-1）/2 = （r+l-1）/2 = （r+l）/2b.l+r为偶数，则r-l为偶数，r-l+1为奇数mid = l+（r-l+1）/2 = l*2/2 + （r-l）/2 =（l+r）/2 = （l+r+1）/2mid = l+（r-l）/2 = l*2/2 + （r-l）/2 = （l+r）/2c.综上所述上述替代成立。Golang二分查找算法的简单实现 http://www.linuxidc.com/Linux/2014-02/96093.htm二分查找改进版 http://www.linuxidc.com/Linux/2013-10/91721.htm二分查找的实现及注意事项 http://www.linuxidc.com/Linux/2013-07/87308.htm用Python实现二分查找 http://www.linuxidc.com/Linux/2012-12/75948.htm二分查找之Java实现 http://www.linuxidc.com/Linux/2012-05/59869.htmJava针对数组的普通查找法和二分查找法 http://www.linuxidc.com/Linux/2012-03/57065.htm本文永久更新链接地址：http://www.linuxidc.com/Linux/2014-09/106594.htm