题目描述

https://leetcode.com/problems/search-insert-position/

样例

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

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

算法1

(暴力枚举)

略去一万字

(二分binary search)

//check条件： 首先我们的check条件因该是找到第一个大于等于target的位置即check if( if (nums[mid] < target) 或者check if (nums[mid] >= target)
//更新： 更新时， if (nums[mid] < target) 我们可以判断结果位置应该在mid右边而且不包含mid如: l = mid +1
//模板： 因此我们套用第一套模板（mid = l + r >> 1不用加1的那套）
//边界： 注意此题需要考虑特殊情况即当所有数都比target小的情况，此时退出的情况是l=r=nums.size()-1，明显我们的结果应该是有边界+1的位置，因此当结果为nums.size()-1时需要特判一下，代码如下：

C++ 代码

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) l = mid + 1;
            else r  = mid;
        }
        if (l == nums.size()-1 && target > nums[l]) l++;
        return l;
    }
};