二分查找在面试中经常被遇到，这个方法十分优雅
介绍
二分查找可以解决（预排序数组的查找）问题：只要数组中包含T（即要查找的值），那么通过不断缩小包含T的范围，最终就可以找到它。一开始，范围覆盖整个数组。将数组的中间项与T进行比较，可以排除一半元素，范围缩小一半。就这样反复比较，反复缩小范围，最终就会在数组中找到T，或者确定原以为T所在的范围实际为空。对于包含N个元素的表，整个查找过程大约要经过log(2)N次比较。（引自编程珠玑）
趣闻
Jon Bentley：90%以上的程序员无法正确无误的写出二分查找代码。
java代码
public int binary_search(int[] array,int n,int value){
//对空值进行判断
if(array == null || n < 1){
return -1;
}
int prev = 0;
int end = n-1;
while(prev <= end){
int middle = prev +(end-prev)/2;
if(array[middle] > value){
end = middle-1;
}else if(array[middle] < value){
prev = middle +1;
}else{
return middle;
}
}
return -1;
}注意
如果end 一开始赋值n，后面代码需要相应的修改
- while（prev < end）
-当array[middle] > value的时候， end = middle;
递归写法
public static int search1(int[] array, int low, int high, int value) {
//对空值进行判断
if(array == null || low > high){
return -1;
}
if(low <= high){
int mid = (low + high) / 2;
if (array[mid] == value) {
return mid;
} else if (array[mid] < value) {
return search1(array, mid + 1, high, value);
} else {
return search1(array, low, mid - 1, value);
}
}else{
return -1;
}
}