二分法,就是所谓的二分查找法,把一个排序好的数组(必须是已排序的),从中间分成两份,取中值与需要查找的值比较,比中值大,则在数组中中值后的段落里继续去除中值比较,直到中值与需要查找的值相同,或者最后取出的段落为1任然不为所要找的值,返回所取中值下标或者找不到时返回-1。
使用while循环的实现
(while循环的实现方式比较容易看懂
/**
* 使用while循环的二分查找
*/
public static int commonBinarySearch(int[] arr,int key){
int low = 0;
int high = arr.length-1;
int middle = 0;
//判断是否有错误数据传入
if(key > arr[high] || key < arr[low] || low > high){
return -1;
}
while (low<=high){
middle = (low + high)/2;
if(arr[middle] < key){
low = middle + 1;
}else if(arr[middle] > key){
high = middle - 1;
}else{
return middle;
}
}
return -1;
}
使用递归的实现
(递归这玩意本质上也就是图一方便,但是咱也不觉着哪儿方便了
/**
* 使用递归的二分查找
*/
public static int recursionBinarySearch(int[] arr,int key,int low,int high){
if(key > arr[high] || key < arr[low] || low > high) {
return -1;
}
int middle = (low + high)/2;
if(arr[middle] < key){
return recursionBinarySearch(arr, key, middle+1, high);
}else if(arr[middle] > key){
return recursionBinarySearch(arr, key, low, middle-1);
}else{
return middle;
}
}
总之二分法就是把一个数组切半切半再切半去查找想要的数值位置