首先根據自己腦子的漿糊先寫一個，再來找問題，
int binarySearch(int* nums, int target, int left, int right){
int mid = (left + right) >> 1;
while(l < r){
if(nums[mid] == target){
return target; //如果是回傳陣列的位置就回傳mid( +- 1)
}else if(nums[mid] > target){
//如果當前中間的數字大于目標，
//說明right需要縮小
right = mid;
return binarySearch(nums, target, left, right);
}else if(nums[mid] < target){
left = mid;
return binarySearch(nums, target, left, right);
}
}
return -1;
}
（其實因為陣列內是按序排序的，可以先判斷target是否小于陣列中最小的數或者大于陣列中最大的數，
很明顯是沒有判定左閉右開或者左開右倍訓是什么其他情況的，單純用腦子我自己繞不清，所以我想直接列資料，
首先假定陣列中的元素都是從小到大排序的，
先判斷陣列選擇是左閉右閉的情況，假設陣列為{0, 1, 2, 3, 4, 5}，我們當前要查找值為3的數在不在陣列中，
【第一輪判斷】令left = 0, right = 5, 則mid = 2(2.5), nums[2] < 3, 所以要把左邊界縮進，left = mid + 1 = 3, (因為現在在判斷左閉右閉的情況，所以要讓left = mid + 1, mid已經判斷過就不再記進去了)，
【第二輪判斷】此時left = 3, right = 5, mid = 4, nums[4] > 3, 所以要把右邊界縮小， right = mid - 1, (同理，判斷過的mid就不算進去了)，
【第三輪判斷】此時left = 3, right = 4, mid = 3(3.5), sum[3] = 3，找到了我們需要找的值為3的數在陣列中，
所以我們寫的while回圈應該是l < r, 不然l == r就無法退出回圈，可實際上已經獲得的準確答案，
再假定陣列選擇是左閉右開的情況，假設陣列為{0, 2, 4, 5, 6}，我們當前要查找值為3的數在不在陣列中，
【第一輪判斷】令left = 0, right = 5(右開), mid = 2(2.5), nums[2] > 3, 所以要把右邊界縮小， right = mid = 2, (因為右開……)，
【第二輪判斷】此時left = 0, right = 2, mid = 1, nums[1] < 3, 所以要把左邊界縮進，left = mid + 1, (因為左閉……)，
【第三輪判斷】此時left = 2, right = 2, mid = 2, nums[2] > 3, 所以要把右邊界縮小, right = mid，
這個時候發現好像陷入死回圈了，那left = right就意味著while回圈也應該寫成l < r, 不然退出不了回圈，
這個時候我突然想是不是我舉例的問題，然后我私底下把以上兩種情況的舉例交換了一下判斷，while陳述句依然應該用l < r來判斷，
暫時不想想左開右閉和左開右開的情況了，感覺也沒必要，始終記左閉右閉這種特殊情況也是ok的，
所以我決定暫時先以左閉右閉為模板來寫二分查找，代碼如下：
int binarySearch(int* nums, int target, int left, int right){
while(l < r){
int mid = ((left + right) >> 2);
//假定陣列是從小到大排序的(即升序)
//判斷target有沒有越界還是寫在外面的函式叭……
if(nums[mid] == target){
return target; //回傳陣列中的位置就回傳mid
}else if(nums[mid] > target){
right = mid - 1;
return binarySearch(nums, target, left, right);
}else if(){
left = mid + 1;
return binarySearch(nums, target, left, right);
}
}
return -1;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/289127.html
標籤：C++