題目：
給定一個排序陣列和一個目標值，在陣列中找到目標值，并回傳其索引。如果目標值不存在于陣列中，回傳它將會被按順序插入的位置。
你可以假設陣列中無重復元素。
示例1：
輸入: [1,3,5,6], 5
輸出: 2
示例2：
輸入: [1,3,5,6], 2
輸出: 1
示例3：
輸入: [1,3,5,6], 7
輸出: 4
示例4：
輸入: [1,3,5,6], 0
輸出: 0
代碼：
int searchInsert(int* nums, int numsSize, int target){
int left = 0, right = numsSize, mid; //這里的right為什么不是被賦值numsSize-1？
while (left < right) {
mid = left + (right - left) / 2;
if (target <= nums[mid]) { //這里的<=可不可以改成=？
right = mid; //既然下面有+1，那這里為什么不-1呢？
}else{
left = mid+1;
}
}
return left;
}
最后能幫我理清這段二分查找代碼的思路嗎？
uj5u.com熱心網友回復：
這種演算法題，最好自己單步除錯一下。理解才會深刻。uj5u.com熱心網友回復：
第二個問題，不能改成等于，要是沒有相等的元素那豈不是就不能二分了uj5u.com熱心網友回復：
int searchInsert(int* nums, int numsSize, int target){//你要理解這里的兩個變數 left right 這代表了陣列的最左邊（即最低值）與最右邊（即最高值）的陣列下標
int left = 0, right = numsSize, mid; //=numsSize你可以理解為加上你輸入的值 比如{1,3,5,6}加一個你輸入的7 最右的下標為4 如果你將值等于numsSize-1那么會導致這個回傳值為3 而不是 4
while (left < right) {
mid = left + (right - left) / 2;
if (target <= nums[mid]) { //上一步將mid賦值 是取陣列中間的值 即 nums[mid] 這里<=nums[mid] 是直接將你輸入的即將插入的target值與中間的值對比
right = mid; //如果你插入的值小于中間值 就將陣列的最右邊right （即最高值）的下標賦值成中間值的mid 即實作二分
}else{
left = mid+1;//如果你插入的值大于中間值 就將陣列的最左邊left （即最低值）的下標賦值成中間值的mid 即實作二分
}
} 經過上面left與right值的重新賦值 也就是說 以前長度為4的陣列變成長度2了 也就可以while回圈取中間的值
return left;
}
二分的理解
舉個例子：
猜數字： 要猜中猜100以內的某個值
你會先猜 50（即target ）
-》小于-》 你就直接丟掉 50以下的值 （即在（ left = mid+1）51 -100 之間繼續猜 ）
-》大于或等于-》你就直接丟掉 50以上的值（即在（right = mid）0-50 之間繼續猜 ）
一直回圈
-》小于-》 你就直接丟掉 75以下的值 （即在（ left = mid+1）76-100 之間繼續猜 ）
-》大于或等于-》你就直接丟掉 25以上的值（即在（right = mid）0-25之間繼續猜 ）
......回圈直到猜中
uj5u.com熱心網友回復：
那最后為什么是return left而不是return right？轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/25936.html
標籤：C語言
下一篇：visual Sudio2010 MFC新建工程型別是“基于對話框”，我添加個選單欄，但是如何添加CMainFrame類？