Task

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

Example 1:

1
2

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

Example 2:

1
2

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

Example 3:

1
2

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

Example 4:

1
2

Input: [1,3,5,6], 0
Output: 0

Solution

  • 有序数组查找元素，直接二分搜索。左右两指针不断缩小范围
  • 时间复杂度：二分搜索O(logn)
  • 空间复杂度：只用到3个指针，O(1)
  • 实现：
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

// Runtime: 4 ms, faster than 99.20% of C++ online submissions for Search Insert Position.
// Memory Usage: 9.6 MB, less than 64.02% of C++ online submissions for Search Insert Position.
class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        //左闭右开区间界定搜索范围
        int l=0,r=nums.size();
        //l<r意味着区间非空
        while(l<r){
            int m=(l+r)/2;
            if(nums[m]==target)
                return m;
            else if(nums[m]>target)
                r=m;
            else
                l=m+1;
        }
        return l;
    }
};