LeetCode 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.

Example 1:

Input: [1,3,5,6], 5
Output: 2
Example 2:

Input: [1,3,5,6], 2
Output: 1
Example 3:

Input: [1,3,5,6], 7
Output: 4
Example 1:

Input: [1,3,5,6], 0
Output: 0
解析：
给定一个已排序的数组和一个目标值，如果目标值存在，则返回对应的下标；如果目标值不存在，则返回目标值应该插入的位置。
采用二分查找，如果找到则返回，如果没有找到，则此时low=high=mid，然后判断target=nums[mid]的大小数值，如果target > nums[mid]则target的插入位置为mid的下一个位置即mid+1，否则插入位置为mid。
此题难度不大，具体代码如下：

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

执行时间如下所示：