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

来源： https://leetcode.com/problems/search-insert-position/

分析

和34题 Search for a range 类似，使用二分查找，得到目标数字，如果目标不在就返回可以插入目标的位置；

边界条件：

当可以插入的位置是arrary的尾部，即需要添加一个位置在尾部，二分查找返回的值需要自增1.

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        if(nums.empty()) return 0;
        int l = 0, r = nums.size() - 1, mid;
        while(l < r){
            mid = (l + r) >> 1;
            if(nums[mid] < target){
                l = mid + 1;
            }
            else{
                r = mid;
            }
        }
        if(nums[l] < target && l == nums.size()-1 )l++;
        return l;
    }
};

null