题目描述

给定一个升序的数组和目标值，如果数组中含有目标值，则返回位置；否则返回插入的位置使得插入后仍满足升序。

假设数组中没有重复元素。

样例

输入：[1,3,5,6], 5
输出：2

输入：[1,3,5,6], 2
输出：1

输入：[1,3,5,6], 7
输出：4

输入：[1,3,5,6], 0
输出：0

算法

(二分) $O(\log n)$

1. 二分查找大于等于目标值的第一个位置。
2. 二分结束后，如果 nums[l] >= target，说明找到了 target 或者 [l, n - 1] 所有元素都比 target 大，则返回 l。
3. 否则说明数组所有元素都比 target 小，返回 n。

时间复杂度

• 二分的时间复杂度为 $O(\log n)$。

空间复杂度

• 仅需要常数的额外空间。

C++ 代码

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

        if (nums[l] >= target)
            return l;

        return n;
    }
};