搜索插入位置

LeetCode 35：用二分查找返回目标下标或有序插入位置。

LeetCode 35 简单数组

发布于 2026.10.13 约 2 分钟阅读浏览 — 次

数组
二分查找
复杂度
Python
变量

题目：35. 搜索插入位置

在无重复元素的升序数组中查找 target。找到时返回下标；未找到时返回按升序插入的位置。这里只计算位置，不修改数组。

1. 查找过程

nums = [1, 3, 5, 6]，target = 2。以下为区间示意，L、M、R 分别表示左边界、中点、右边界。

第 1 轮

代码块 Text

1
2
3
4
index:  0   1   2   3
value:  1   3   5   6
        ●───●───●───●
        L   M       R

middle = 1，nums[1] = 3 > 2，排除下标 1～3，更新 right = middle - 1，即 right = 0。

第 2 轮：只检查下标 0

代码块 Text

1
2
3
4
index:  0
value:  1
        ●
      L=M=R

middle = 0，nums[0] = 1 < 2，更新 left = middle + 1，即 left = 1。此时 left = 1 > right = 0，候选区间为空，结束查找。

关键提示：在当前左闭右闭写法中，left 左侧的元素都小于 target，right 右侧的元素都大于 target。未找到目标值时，left = right + 1，两侧边界刚好交错，left 正是插入位置；这里也可以写成 return right + 1。

2. Python 实现

代码块 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
25
def search_insert(nums, target):
    left, right = 0, len(nums) - 1

    while left <= right:
        middle = (left + right) // 2
        if nums[middle] > target:
            right = middle - 1
        elif nums[middle] < target:
            left = middle + 1
        else:
            return middle
    return left


nums = [1, 3, 5, 6]
print(search_insert(nums, 5))
print(search_insert(nums, 2))
print(search_insert(nums, 7))
print(search_insert(nums, 0))

# 输出：
# 2
# 1
# 4
# 0

3. 复杂度

时间复杂度：最坏为 O(log n)，每轮候选区间缩小约一半。
额外空间复杂度：O(1)，只维护固定数量的下标变量。

使用 GitHub 登录后参与讨论，评论将公开保存在 GitHub。

阅读到这里时加载评论。