题目链接：35.搜索插入位置

题解：

同样是二分！

题目简述：

给一个有序数组，查找目标值的位置，若数组中存在，返回该下标，否则返回目标值应该插入的位置！

题解：

继续二分：

找到二分条件：x >= target，右端满足，左端不满足！

如果最终该目标值越界，即nums[r] < target，直接返回r + 1或nums.size()。

会发现：其实直接使用右端点r = nums.size()二分即可！最后也可以不用判断是否越界！

AC代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int l = 0, r = nums.size() - 1;
        while(l < r){
            int mid = l + r >> 1;
            if(nums[mid] >= target) r = mid;
            else l = mid + 1;
        }
        if(nums[r] < target) return r + 1;
        return r;
    }
};

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