題目描述
給定一個(gè)排序數(shù)組和一個(gè)目標(biāo)值槽棍，在數(shù)組中找到目標(biāo)值轨淌，并返回其索引火的。如果目標(biāo)值不存在于數(shù)組中猴贰，返回它將會(huì)被按順序插入的位置。
你可以假設(shè)數(shù)組中無(wú)重復(fù)元素怜庸。
示例
示例 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
題目分析
二分搜索應(yīng)用当犯，需要注意搜索邊界的處理，即一開(kāi)始如果令low=0,high=n-1,則二分搜索的區(qū)間是閉區(qū)間[0,n-1]割疾，后面變換high或者low的值時(shí)也應(yīng)該一直保持搜索區(qū)間是完全閉合的狀態(tài)嚎卫，即high=mid-1。如果令low=0,high=n,則二分搜索區(qū)間是[0,n)杈曲，左閉右開(kāi)驰凛，后面變換high時(shí)胸懈，應(yīng)該令high=mid担扑，一直保持左閉右開(kāi)的搜索區(qū)間。
C++代碼
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int n = nums.size();
int low = 0;
int high = n-1;
while(low <= high){
int mid = low + (high-low)/2;
if (target < nums[mid]){
high = mid-1;
}
else if (target > nums[mid]){
low = mid+1;
}
else{
return mid;
}
}
return low;
}
};
