【Leetcode Daily】35搜索插入位置

题目浅析

• 想查看原题可以点击题目链接。

• 简单地说，给一个升序的无重复元素数组和目标值，找到该值的下标，如果数组中无目标值，则返回应该插入的地方

思路分享

• 基本思路可看【Leetcode Daily】34在排序数组中查找元素的第一个和最后一个位置。

• 回到本题，要求这个“位置”，其实就是左指针，因为左指针确保 left-1 小于 target，循环到最后，left 本身一定是 target 应该所属的位置。

• 此外，c++ 的 ranges 库自带二分的低边界，可以写ranges::lower_bound(nums, target)来得到指向目标值左侧边界的迭代器，减去起始迭代器 begin() 就得到下标了。

代码解答（强烈建议自行解答后再看）

• 参考题解

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int left = 0, right = nums.size(), middle = 0;
        while(left < right) {
            middle = left+(right-left)/2;
            if(nums[middle]<target) {
                left = middle+1;
            }
            else {
                right = middle;
            }
        }
        return left;
        // return ranges::lower_bound(nums, target)-nums.begin();
    }
};