35.Search Insert Position
Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.
You may assume no duplicates in the array.
Here are few examples.
[1,3,5,6], 5 → 2
[1,3,5,6], 2 → 1
[1,3,5,6], 7 → 4
[1,3,5,6], 0 → 0
典型的Binary-Search，第一版思路是先用Binary-Search，如果没找到，再从最后出发向前遍历直到找到恰好比target大的元素并返回，代码如下:
/*solution1*/
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
if(nums.empty()||target<nums[0])
return 0;
int low=0,size=nums.size(),high=size-1,mid=0,i=0;
while(low<=high){
mid=low+(high-low)/2;
if(nums[mid]==target)
return mid;
if(nums[mid]>target)
high=mid-1;
else
low=mid+1;
}
// if not found,let varible i go back to find an exact position
for(i=size;i>=0&&nums[i-1]>target;i--);
return i;
}
};
之后又看了一些别人写的代码，发现最后一步向前查找是不必要的，因为Binary-Search的性质是如果最后找不到目标元素，则low指针指向恰好比target大的元素;high指针指向恰好比target小的元素，所以代码可以优化如下:
/*solution2*/
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
if(nums.empty()||target<nums[0])
return 0;
int low=0,size=nums.size(),high=size-1,mid=0,i=0;
while(low<=high){
mid=low+(high-low)/2;
if(nums[mid]==target)
return mid;
if(nums[mid]>target)
high=mid-1;
else
low=mid+1;
}
// if not found
return low;
}
};