對(duì)于程序猿或者程序媛來(lái)講郁季，二分查找貌似并不陌生主要是循環(huán)遍歷一個(gè)有序的數(shù)組找到你想要的元素。二分查找gitHub，具體圖解如下：
image
當(dāng)時(shí)我的想法是這就是個(gè)簡(jiǎn)單的遞歸算法豺旬，每次查詢array[array.length/2] == number
判斷第ary.length/2個(gè)元素的值是否與number相等霉翔，并返回arry中的位置睁蕾。廢話不多說(shuō)了，直接上代碼
//在ary中通過(guò)二分查找的方式找到對(duì)應(yīng)數(shù)字在ary中的位置
public static int getOneNumberBayHalf(int [] ary,int number,int start, int end){
if(start> end)
return -1;
int mid = start +(end -start)/2;
if (number == ary[mid]) {
System.out.print("數(shù)字:" + number+"的位置在從ary中的第"+mid+"位");
return mid;
}
if (number < ary[mid]){
return getOneNumberBayHalf(ary,number,start,mid-1);
}
//if (number > ary[mid])
else {
return getOneNumberBayHalf(ary,number,mid+1,end);
}
}
遞歸算法如果沒(méi)設(shè)計(jì)好推出邏輯很容易出現(xiàn)stackoverflow债朵。確實(shí)是這樣子眶，我一開(kāi)始把出口邏輯寫(xiě)錯(cuò)了。如下（以下是典型錯(cuò)誤示范序芦，所以大家一定要注意）：
public static int binarySearch(int[] array, int target) {
int low = 0, high = array.length - 1;
while (low < high) {
int mid =(high - low) / 2;
if (target == array[mid]) {
return mid;
} else if (target > array[mid]) {
low = mid + 1;
} else if (target < array[mid]) {
high = mid;
}
}
return -1;
}
執(zhí)行的時(shí)候直接死循環(huán)了臭杰，畢竟是干QA的直接發(fā)現(xiàn)邏輯有問(wèn)題于是被我優(yōu)化了一下，如下：
public static int binarySearch(int[] array, int target) {
int low = 0, high = array.length - 1;
while (low < high) {
// 下面代碼一定注意,否則會(huì)進(jìn)入死循環(huán)
// int mid =(high - low) / 2;
// 正確寫(xiě)法如下
int mid =low + (high - low) / 2;
if (target == array[mid]) {
return mid;
} else if (target > array[mid]) {
low = mid + 1;
} else if (target < array[mid]) {
high = mid;
}
}
return -1;
}
希望看完這篇文章的QA同學(xué)們以后都要注意一下開(kāi)發(fā)的寫(xiě)法谚中，尤其是對(duì)循環(huán)渴杆、判斷、遞歸出口等宪塔，一定要注意一下磁奖，及時(shí)發(fā)現(xiàn)問(wèn)題并指正！
