重温二分查找算法-白红宇

二分查找在学习算法的时候会涉及到，算是一个基本的分治思想，对于算法的实现大家也都是很熟悉的，但是这个时候真会犯眼高手低的毛病。不信你自己试试，看你能够在段时间内写出可运行的二分查找算法。

二分查找算法的思想非常易于理解，但是能够写出一个准确的二分查找程序绝非一个很简单的事情，从历史上来看，二分思想早在1946年就出现了，但是第一个完全正确的二分查找算法确实在1962年出现，计算机专家曾说过，90%以上的计算机专家不能再2个小时内写出完全正确的二分查找算法。我反正是应了这句话，不过我不是计算机专家。

我们来看一个比较标准的二分查找算法

点击(此处)折叠或打开

package new_test;
public class BinarySearch {

int arr[];
public static void main(String args[]){

test();
}
public int binarySearch(int t,int[] arr){

int left=0;
int right=arr.length;
int middle;
while(left middle=(left+right)/2;
if(t==arr[middle]){

return middle;
}
if(t>arr[middle]){

left=middle+1;
}
if(t right=middle-1;
}
}
return -1;
}
public static void test(){

int[] arr=new int[]{1,2,5,7,8,10,11,15,19,20};
System.out.println( new BinarySearch().binarySearch(8, arr));
}
}

运行结果是4，即arr[4]=8

其实这个算法还有一些值得思考的细节。比如求得两个数之和的平均数

如果直接写为middle=(left+right)/2就很可能出现数值溢出的情况。

可以使用下面的形式来避免，算法博大精深，细节决定成败。

middle=left+(right-left)/2;