搜索插入位置

题意

给定升序无重复数组 nums 和目标值 target，返回 target 在数组中的索引；若不存在，返回按顺序插入的位置。要求 $O(\log n)$ 。

思路

本题本质是求 lower_bound：区间内第一个 $\geqslant \text{target}$ 的位置。C++ 直接调用 lower_bound；Python 手写二分，谓词 nums[m] >= target 缩右区间，nums[m] < target 缩左区间。

关键理解：lower_bound 返回的位置既是"已存在元素的索引"（若该元素等于 target），也是"应插入的位置"（若不存在）。二者统一在同一次二分中。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int searchInsert(vector<int> &nums, int target) {
        return lower_bound(nums.begin(), nums.end(), target) - nums.begin();
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, t;
    cin >> n >> t;
    vector<int> a(n);
    for (int &x : a)
        cin >> x;
    cout << Solution().searchInsert(a, t) << '\n';
    return 0;
}

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24#!/usr/bin/env python3
from typing import List


class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        lo, hi = 0, len(nums)
        while lo < hi:
            m = (lo + hi) // 2
            if nums[m] >= target:
                hi = m
            else:
                lo = m + 1
        return lo


def main():
    n, t = map(int, input().split())
    a = list(map(int, input().split()))
    print(Solution().searchInsert(a, t))


if __name__ == "__main__":
    main()

复杂度

时间复杂度： $O(\log n)$ 。
空间复杂度： $O(1)$ 。

总结

lower_bound 是二分查找的基础操作：找第一个满足谓词的位置。本题谓词是 $\geqslant \text{target}$ ，返回值同时覆盖"找到"和"插入"两种语义。

目录

题意

思路

代码

复杂度

总结