搜索插入位置 图解题解

搜索插入位置到底要返回哪个下标

给一个升序、无重复的数组 nums 和目标值 target。target 在数组里就返回它的下标；不在就返回它该插入的位置。题面例子：nums=[1,3,5,6]、target=5 返回 2、target=2 返回 1。两种情形是同一个问题：都在问「第一个大于等于 target 的数排第几」，这个下标叫 lower_bound（第一个不小于目标的位置）。

一个个往后比，为什么对不起这个有序数组

挨个往后比，最坏要看遍 n 个数，是 O(n) 的线性扫。可数组明明升序，「≥ target」一旦成立往右就一直成立、左边一律不成立，线性扫把这条性质白扔了。一刀两断的结构，用二分查找在 O(log n) 里解决。

凭什么这个数组能二分

二分要成立，得有一条把区间劈两半的单调性质，这里就是「nums[i] ≥ target 吗」。数组升序，这个判断从某个位置起由「否」翻成「是」、再不翻回：左边全小于 target，右边全大于等于 target。插入位置就是这条分界线上「是」的第一个格子，每看一个中点砍掉一半。

mid 合格时，右界为什么收 mid 不收 mid−1

把范围定成左闭右开区间 [l, r)（含 l、不含 r），起手 l=0、r=n。r 取长度 n 而非 n−1，因为插到末尾时下标正好是 n。取中点 mid=(l+r)//2 比 target：nums[mid] ≥ target 时够大、可能是答案，右界收到 mid（写 r=mid 不是 mid−1，留住它）；nums[mid] < target 时它和左边全太小，左界写 l=mid+1 跳过。循环到 l==r，l 停处就是第一个 ≥ target 的下标。答案自始至终留在 [l, r) 里。

题面两个例子，逐轮收区间

先看 target=5、nums=[1,3,5,6]，l=0、r=4。第一轮 mid=2，nums[2]=5≥5，收 r=2，区间 [0,2)。第二轮 mid=1，nums[1]=3<5，收 l=2，区间 [2,2)。l==r=2 退出，返回 2。

再看不存在的 target=2。l=0、r=4。第一轮 mid=2，5≥2，r=2。第二轮 mid=1，3≥2，r=1。第三轮 mid=0，nums[0]=1<2，l=1，区间 [1,1)。l==r=1 退出，返回 1。

右界起手用 n−1，末尾那个位置就没了

右界起手写成 n−1 最常见：右开区间本就够不到下标 n，target 大过所有数、该插到末尾时就返回不出 n，末尾那个位置凭空没了。收缩写反也坑：nums[mid] ≥ target 时手滑写 r=mid−1，会把可能是答案的 mid 丢掉。循环条件要配对：左闭右开用 while l<r，错成 l<=r 又不动 r，l==r 那轮空转成死循环。mid 用 (l+r)//2 数值极大时会溢出，稳妥写 l+(r−l)//2。收尾复杂度：每轮把区间对半砍，最多 log₂n 次收空，时间 O(log n)；只用 l、r、mid 三个下标，空间 O(1)。

Python

def searchInsert(nums, target):
    l, r = 0, len(nums)        # r 取 n：插入位可到末尾之后
    while l < r:
        mid = (l + r) // 2
        if nums[mid] >= target:
            r = mid             # mid 合格，留在候选内
        else:
            l = mid + 1         # mid 太小，排除
    return l                   # 第一个 >= target 的下标

C++

int searchInsert(vector<int>& nums, int target){
    int l = 0, r = nums.size();      // r 取 n
    while(l < r){
        int mid = l + (r - l) / 2;   // 防溢出
        if(nums[mid] >= target) r = mid;   // 合格，缩右
        else l = mid + 1;            // 太小，排除
    }
    return l;
}

Java

public int searchInsert(int[] nums, int target) {
    int l = 0, r = nums.length;        // r 取 n
    while (l < r) {
        int mid = l + (r - l) / 2;     // 防溢出，等价 (l+r)/2
        if (nums[mid] >= target) {
            r = mid;                   // mid 合格，留在候选内
        } else {
            l = mid + 1;               // mid 太小，排除
        }
    }
    return l;                          // 第一个 >= target 的下标
}