力扣百题通

35. 搜索插入位置 (Easy)

Properties2
description给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。
tags09-二分查找

8分钟阅读

35. 搜索插入位置 (Easy)

专题归类： 09-二分查找 LeetCode 链接： https://leetcode.cn/problems/search-insert-position/

在线做题： 写 Python 代码并运行 · Java 跳转 LeetCode

题目描述

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在，返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 O(log n) 的算法。

示例 1：

输入：nums = [1,3,5,6], target = 5
输出：2

示例 2：

输入：nums = [1,3,5,6], target = 2
输出：1

示例 3：

输入：nums = [1,3,5,6], target = 7
输出：4

示例 4：

输入：nums = [1,3,5,6], target = 0
输出：0

提示：

  • 1 <= nums.length <= 10^4
  • -10^4 <= nums[i] <= 10^4
  • nums 为无重复元素的升序排列数组
  • -10^4 <= target <= 10^4

题目详细分析

数据范围含义：

  • nums.length <= 10^4：O(log n) 二分最多 14 次比较，非常快。
  • 无重复元素：简化了查找——每个值最多出现一次，不需要处理重复。
  • 升序排列：二分查找的前提条件。

问题本质：

  • 这是一个”查找左边界”问题——找第一个 >= target 的元素位置。
  • 如果 target 存在，返回其索引（第一个等于 target 的位置）。
  • 如果 target 不存在，返回它应该插入的位置（第一个大于 target 的位置）。
  • 插入位置的范围是 [0, len(nums)]，包括在开头（所有元素都大）和在末尾（所有元素都小）。

边界条件：

  • target 小于所有元素 → 返回 0。
  • target 大于所有元素 → 返回 len(nums)（插入到末尾）。
  • target 等于某个元素 → 返回该元素索引。

小白版直白理解

就像翻字典查单词：

  • 字典是排好序的（a → z）。
  • 如果要查的单词存在，就告诉你它在哪一页。
  • 如果不存在，就告诉你它应该插在哪一页之间。

比如在 [1,3,5,6] 中找 2：

  • 先看中间 5，2<5，所以在前半段 [1,3] 中找。
  • 再看中间 1，2>1，所以在后半段 [3] 中找。
  • 再看 3，2<3，所以 2 应该插在 1 和 3 之间，位置是 1。

解题思路

思路一：左闭右闭区间二分（推荐）

核心思想： 维护 [left, right] 闭区间，每次排除一半不可能的区域。循环结束时，left 就是第一个 >= target 的位置。

关键洞察： 当 nums[mid] < target 时，mid 及左侧都 < target，一定能被排除，所以 left = mid + 1；否则（nums[mid] >= target），mid 可能是答案，所以 right = mid - 1，但 left 不会越过这个位置。

搜索过程可视化（以 nums=[1,3,5,6], target=2 为例）：

初始: left=0, right=3
第1步: mid=1, nums[1]=3 >= 2, right=0
第2步: mid=0, nums[0]=1 < 2, left=1
第3步: left=1 > right=0, 退出
返回 left=1

def searchInsert(nums, target):
    left, right = 0, len(nums) - 1
 
    while left <= right:
        mid = left + (right - left) // 2
        if nums[mid] == target:
            return mid  # 找到目标，直接返回
        elif nums[mid] < target:
            left = mid + 1  # 目标在右半
        else:
            right = mid - 1  # 目标在左半
 
    # 循环结束时 left > right，left 即插入位置
    return left

思路二：左边界二分模板

核心思想： 统一使用”找第一个 >= target 的位置”的二分模板，不论 target 是否存在，结果都是正确的。

def searchInsert(nums, target):
    left, right = 0, len(nums) - 1
 
    while left <= right:
        mid = left + (right - left) // 2
        if nums[mid] < target:
            left = mid + 1  # mid 太小，收缩左边界
        else:
            right = mid - 1  # nums[mid] >= target，收缩右边界
 
    return left  # left 就是第一个 >= target 的位置

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

易错点

  1. 区间不变量搞混：使用 left <= right（闭区间）时，更新为 mid + 1 / mid - 1；使用 left < right（开区间）时，更新方式不同。统一使用一种风格避免混淆。
  2. 返回 left 还是 right：循环结束时，left 是第一个 >= target 的位置；right 是 left - 1。要注意返回的是 left。
  3. 越界风险：mid = (left + right) // 2 在 left+right 很大时可能溢出，用 left + (right - left) // 2 更安全。
  4. 死循环：当 left == right 时，如果更新逻辑不恰当（例如 left = mid 而不是 mid + 1），可能出现死循环。使用 left <= right 闭区间的风格，配合 mid +/- 1 的更新，不会死循环。
  5. 插入末尾：如果 target 大于所有元素，最终 left = len(nums)，这就是插入到末尾的位置，不能越界访问 nums[left]。

框架提炼

二分查找左闭右闭模板：

def binary_search(nums, target):
    left, right = 0, len(nums) - 1
 
    while left <= right:  # 闭区间 [left, right]
        mid = left + (right - left) // 2
 
        if nums[mid] == target:
            return mid          # 查找精确值
        elif nums[mid] < target:
            left = mid + 1      # 排除左半
        else:
            right = mid - 1     # 排除右半
 
    # left 是第一个 > target 的位置（即插入位置）
    return left

三种典型二分场景：

场景返回条件典型题目
精确查找nums[mid] == target 时返回 mid704-二分查找
找左边界找第一个 >= target，返回 left35-搜索插入位置
找右边界找最后一个 <= target，返回 right34-查找元素首末位置

关键记忆： 二分查找的本质是不断缩小”目标可能存在”的区间，关键在于每次排除一半的确定无效区域。

关联题目

关系图谱

反向链接