二分算法是我們經常會用到的一個算法。它是分治法的一個應用。不過，雖然他寫起來貌似很簡單，但是卻很容易寫錯。下面我們討論一下二分的死循環問題。（這裡討論的是整數的二分問題，浮點數的二分不容易死循環）
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)/2
mid = l+(r-l)/2 = l*2/2 + (r-l-1)/2 = (r+l-1)/2 = (r+l)/2
b.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)/2
mid = l+(r-l)/2 = l*2/2 + (r-l)/2 = (l+r)/2
c.綜上所述上述替代成立。
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.htm
Java針對數組的普通查找法和二分查找法 http://www.linuxidc.com/Linux/2012-03/57065.htm
