先與l+(r-l)/2處比較就是中間位置比較，為什么不是（l+r）/2呢，因?yàn)閘+r相加有可能會(huì)發(fā)生溢出。
小于中間位置，則在左邊位置繼續(xù)重復(fù)上一步，大于則在右邊重復(fù)，如此重復(fù)即可。
public static int find(Comparable[] arr, Comparable target) {
// 在arr[l...r]之中查找target
? ? int l =0, r = arr.length-1;
? ? while( l <= r ){
//int mid = (l + r)/2;
? ? ? ? // 防止極端情況下的整形溢出，使用下面的邏輯求出mid
? ? ? ? int mid = l + (r-l)/2;
? ? ? ? if( arr[mid].compareTo(target) ==0 )
return mid;
? ? ? ? if( arr[mid].compareTo(target) >0 )
r = mid -1;
else
? ? ? ? ? ? l = mid +1;
? ? }
return -1;
}
遞歸實(shí)現(xiàn)
private static int find(Comparable[] arr, int l, int r, Comparable target){
if( l > r )
return -1;
? ? //int mid = (l+r)/2;
? ? // 防止極端情況下的整形溢出，使用下面的邏輯求出mid
? ? int mid = l + (r-l)/2;
? ? if( arr[mid].compareTo(target) ==0 )
return mid;
? ? else if( arr[mid].compareTo(target) >0 )
return find(arr, l, mid-1, target);
else
? ? ? ? return find(arr, mid+1, r, target);
}
