第6章｜二分、堆与优先队列

Unit 02 · LeetCode #35

← Unit 01
仅本次页面有效
35
Search Insert PositionBoundary · Lower Bound

没有命中目标，
不代表二分没有找到答案。

插入位置是“第一个不小于target的位置”。目标不存在时，左右边界仍会收敛到唯一合法缝隙；目标存在时，这个边界恰好就是目标下标。

检测到上次学习记录可以恢复阶段、边界状态、代码、迁移进度和滚动位置。
LeetCode #35 原题内容题面转述、边界定义与复杂度

题目要求

给定一个按升序排列且元素互不相同的整数数组 nums 和目标值 target。若目标存在，返回其下标；否则返回目标按顺序插入数组时的位置。

要求算法时间复杂度为 O(log n)。

class Solution: def searchInsert( self, nums: List[int], target: int ) -> int: pass

约束

  • 1 ≤ nums.length ≤ 10⁴；
  • -10⁴ ≤ nums[i], target ≤ 10⁴；
  • nums严格递增。

官方示例

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

本页主方法

寻找第一个满足 nums[i] ≥ target 的位置。使用半开候选区间 [left,right)，其中 right 可等于 len(nums)。时间复杂度 O(log n)，空间 O(1)。

从 Unit 01 精确查找到 Unit 02 边界查找：不再问“有没有”，而是问“切换点在哪里”

Unit 01 · 精确命中

比较后立即处理“小于、等于、大于”；候选是已有元素下标，失败时区间最终为空。

→
Unit 02 · Lower Bound

把每个位置染成 False / True，始终寻找第一个 True；答案还可能是数组末尾的虚拟位置 n。

插入缝隙

长度为n的数组存在n+1个插入位置：元素之前、元素之间以及最后一个元素之后。

Lower Bound

第一个使 nums[i] ≥ target 成立的位置，也称第一个不小于目标的位置。

半开区间

[left,right)包含left但不包含right，候选数量为 right-left。

虚拟位置 n

若所有元素都小于target，答案是 len(nums)；它是合法插入位置，但不是已有元素下标。

nums = [1,3,5,6]target = 2
left=0
mid=2
right=4（不包含）
target=2
本轮边界证据

判断nums[mid]是否已经进入“≥target”的True区域。

当前边界契约 答案是第一个nums[i] ≥ target的位置；若不存在则为n。

区间演化记录

nums[mid]5
谓词nums[mid]≥targetTrue
候选数量right−left4
收敛答案—

边界不变量

第一个不小于target的位置始终位于半开区间 [left,right) 中；right本身是区间外的边界标记。

mid是否保留

若nums[mid]≥target，mid仍可能是第一个True，因此执行right=mid；若nums[mid]<target，mid必然过小，执行left=mid+1。

候选插入位置5
已完成判断0
False区域长度1
True区域长度3
当前结果未收敛
同一个返回值覆盖“命中”和“未命中”

Lower Bound不需要在循环中区分目标是否存在。它始终返回第一个不小于target的位置，最后再观察该位置的值即可判断是否命中。

区间语义混用会删除答案或访问越界

在半开区间中，right不属于候选，因此循环使用left<right；当mid进入True区域时必须保留mid，执行right=mid。

错误：right = mid - 1

若mid恰好是第一个True，会直接删除正确答案。半开区间右端只需移动到mid。

错误：while left <= right

right可等于n且不属于数组下标，闭区间循环可能尝试访问nums[n]。

边界搜索自然覆盖三个极端

答案可以位于第一个元素之前、数组内部，也可以位于最后一个元素之后。

target=0
所有元素≥0
答案=0
target=4
3<4≤5
答案=2
target=7
所有元素<7
答案=n=4
补全LeetCode提交代码Lower Bound半开区间
class Solution:
def searchInsert(self, nums, target) -> int:
left =
right =
while :
mid =
if nums[mid] < target:
else:
return
分层提示：每次只展开一层，不直接给出完整提交代码
第 1 层｜答案空间包含 gap n，因此右边界初始化为 len(nums)。
第 2 层｜半开区间仍有候选元素时满足 left < right。
第 3 层｜nums[mid] < target 说明 mid 属于 False 区域，必须连同 mid 一起排除。
第 4 层｜否则 mid 已进入 True 区域，但仍可能是第一个 True，所以只能令右端移动到 mid。
第 5 层｜退出时 left == right，该位置就是唯一边界，不必再次访问数组。
为什么可以直接返回left？循环退出时left==right，候选区间只剩一个边界位置。所有左侧位置都已证明小于target，当前位置及右侧属于不小于target区域，或当前位置正好是n。
代码—插入缝隙—False/True边界联动示例target=2
1class Solution:
2 def searchInsert(self, nums, target):
3 left = 0
4 right = len(nums)
6 while left < right:
7 mid = left + (right-left)//2
9 if nums[mid] < target:
10 left = mid + 1
12 right = mid
14 return left
播放后观察：[0,4)依次缩为[0,2)、[0,1)、[1,1)，最终返回插入缝隙1。
完成代码联动后进入首尾位置迁移只有代码全部正确或播放完整轨迹后解锁；提示和初始化骨架不会解锁。
迁移题：LeetCode #34《在排序数组中查找元素的第一个和最后一个位置》

不要直接从空白背两套二分。先把 #35 的“第一个 ≥ target”扩展为两个边界：第一个 ≥ target 与第一个 > target。

官方题意

给定一个按非递减顺序排列的整数数组 nums 和目标值 target，返回目标值在数组中的起始与结束位置；若目标不存在，返回 [-1,-1]。算法必须达到 O(log n)。

class Solution: def searchRange( self, nums: List[int], target: int ) -> List[int]: pass
打开 LeetCode 官方原题 ↗

官方示例与约束

nums=[5,7,7,8,8,10], target=8
输出：[3,4]
nums=[5,7,7,8,8,10], target=6
输出：[-1,-1]
nums=[], target=0
输出：[-1,-1]
  • 0 ≤ nums.length ≤ 10⁵
  • 数组按非递减顺序排列，允许重复值
  • -10⁹ ≤ nums[i], target ≤ 10⁹
读题检查 1｜空数组时应返回什么？
读题检查 2｜为什么不能命中一个 8 就直接返回？
两项读题检查都完成后，才进入结构对照。
#35 搜索插入位置#34 首尾位置
数组严格递增数组非递减，目标可能重复
只求 lower_bound(target)同时求 lower_bound(target) 与 upper_bound(target)
答案允许为 n左边界越界或不等于 target 时返回 [-1,-1]
True 谓词：nums[i] ≥ target右边界外侧谓词：nums[i] > target
按依赖顺序拼接完整策略
先求左边界，再验证存在性；只有目标存在才需要求右边界外侧。
槽位 1 · Lower Bound 的 False 分支在 lower_bound(value) 中，什么条件下向右排除？
槽位 2 · 存在性检查first 何时不能代表目标首位置？
槽位 3 · Upper Bound 的 False 分支寻找第一个 > value 时，哪些位置必须向右排除？
槽位 4 · 闭合结果区间若 right_exclusive = upper_bound(target)，最后位置是什么？
first = lower_bound(target) if first 越界或 nums[first] != target: return [-1, -1] right_exclusive = upper_bound(target) return [first, right_exclusive - 1]
四个语义槽位都正确后，才进入官方样例。

官方样例：nums=[5,7,7,8,8,10], target=8

phasesetup
区间[0,6)
mid / value—
谓词—
first—
right exclusive—
先寻找第一个 nums[i] ≥ 8 的位置。
独立重写：实现两个边界，不提供占位符或完整答案先运行完整样例
完整运行样例后，编辑器与检查按钮才会开放。
完成后停留在本页

不会自动跳转。可以继续重放 Lower/Upper Bound 轨迹，或手动进入下一单元。

手动进入 Unit 03 →

第6章 Unit 02 Skill卡

搜索插入位置把二分从“是否命中”升级为“状态边界在哪里”。Lower Bound统一处理目标存在、目标缺失和插入到数组末尾的情况。

题号与题型#35｜Lower Bound边界搜索
目标定义第一个nums[i]≥target的位置；不存在则为n
候选空间半开区间[left,right)，初始right=n
核心谓词nums[i]≥target：False…False,True…True
核心更新False：left=mid+1；True：right=mid
终止条件left==right，唯一边界位置
复杂度时间O(log n)，空间O(1)
常见错误True时删除mid；把n当成非法答案；混用闭区间循环
推荐下一题#153 寻找旋转排序数组中的最小值