二分法寞焙，就是所謂的二分查找法，把一個(gè)排序好的數(shù)組（必須是已排序的）聂示，從中間分成兩份域携，取中值與需要查找的值比較，比中值大鱼喉，則在數(shù)組中中值后的段落里繼續(xù)去除中值比較，直到中值與需要查找的值相同趋观，或者最后取出的段落為1任然不為所要找的值扛禽，返回所取中值下標(biāo)或者找不到時(shí)返回-1。
使用while循環(huán)的實(shí)現(xiàn)
（while循環(huán)的實(shí)現(xiàn)方式比較容易看懂
/**
* 使用while循環(huán)的二分查找
*/
public static int commonBinarySearch(int[] arr,int key){
int low = 0;
int high = arr.length-1;
int middle = 0;
//判斷是否有錯(cuò)誤數(shù)據(jù)傳入
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;
}
使用遞歸的實(shí)現(xiàn)
(遞歸這玩意本質(zhì)上也就是圖一方便皱坛，但是咱也不覺(jué)著哪兒方便了
/**
* 使用遞歸的二分查找
*/
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;
}
}
總之二分法就是把一個(gè)數(shù)組切半切半再切半去查找想要的數(shù)值位置
