35. 搜索插入位置#

1
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。
2

3
如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
4

5
请必须使用时间复杂度为 O(log n) 的算法。
6

7

8

9
示例 1:
10

11
输入: nums = [1,3,5,6], target = 5
12
输出: 2
13
示例 2:
14

15
输入: nums = [1,3,5,6], target = 2
16
输出: 1
17
示例 3:
18

19
输入: nums = [1,3,5,6], target = 7
20
输出: 4
21
示例 4:
22

23
输入: nums = [1,3,5,6], target = 0
24
输出: 0
25
示例 5:
26

27
输入: nums = [1], target = 0
28
输出: 0
29

30

31
提示:
32

33
1 <= nums.length <= 10^4
34
-10^4 <= nums[i] <= 10^4
35
nums 为无重复元素的升序排列数组
36
-10^4 <= target <= 10^4

1
class Solution {
2
public:
3
    int searchInsert(vector<int>& nums, int target) {
4
        int n = nums.size();
5
        int l = 0, r = n - 1;
6
        int mid = 0;
7
        while(l <= r)
8
        {
9
            mid = l + (r - l) / 2;
10
            if(nums[mid] == target) return mid;
11
            else if(nums[mid] > target) r = mid - 1;
12
            else l = mid + 1;
13
        }
14
        return l == mid + 1 ? l : mid;
15
    }
16
};