ALGORITHM NOTEBOOK / PYTHON 3

二分查找
从区间不变量，到中位数划分

9 道题，建立一套能解释、能手写、能迁移的搜索方法。先证明为什么能删掉一半，再写边界；用逐轮推演检查每一次收缩。

09指定题目全覆盖

05循序渐进的阶段

18完整 Python 解法

使用方式：先看题意并尝试 15–25 分钟，再核对不变量、代码与推演；闭卷重写后标记“已掌握”。目录可按题号、名称或知识点搜索。所有内容离线可读，只有主动打开原题链接需要联网。

建议的学习顺序

阶段	题目顺序	达成目标
01 · 基础模板	704 → 35	从精确命中走向插入边界
02 · 边界与答案	34 → 69	重复段与数值可行性
03 · 矩阵应用	74 → 240	先确认有序条件，再选择搜索方法
04 · 旋转数组	153 → 33	先找断点，再识别有序半边
05 · 进阶划分	4	把中位数转化为满足约束的切口

基础知识：二分的前提是可排除性

典型二分依赖随机访问与单调结构。数组全局有序时，可凭中点大小排除一半；答案域上则需构造单调的可行性判定。旋转数组不全局有序，但可以识别有序半边；第 240 题每步删一行或一列，是同一排除思想下的阶梯搜索。

定义候选 → 判断中点 → 证明排除安全 → 确保严格收缩 → 解释退出值

不变量：每轮开始和结束都保持为真的陈述。例如“如果目标存在，它仍在 [left,right] 内”。
终止性：用区间长度衡量进度；每轮长度必须严格下降。
复杂度：候选规模约为 n/2ᵏ，缩到 1 约需 log₂n 轮。不要在每轮切片或线性扫描。
返回语义：精确查找可能失败；边界查找一定返回 [0,n] 中的插入点；收敛查找在非空候选里保留一个答案。

三种区间约定对照

任务	初始化	循环	偏小时 / 偏大时	退出含义
闭区间精确查找	left=0,right=n−1	left≤right	left=mid+1 / right=mid−1	空区间，未命中则 -1
左闭右开边界	left=0,right=n	left<right	按判定：left=mid+1 / right=mid	left=right，是分割点，可等于 n
闭区间收敛最小值	left=0,right=n−1	left<right	按性质：left=mid+1 / right=mid	唯一剩余候选，返回 nums[left]

不要只背 left<right 或 right=mid：相同循环形式可以表达不同任务。以第 153 题为例，候选是闭区间 [left,right]；lower_bound 则以 [left,right) 表示尚未分类的元素，答案分割点可位于 n。

核心模板：把边界统一成单调判定

三个模板均保留完整的 class Solution 提交入口：A 对应 704，B 对应 35，C 对应 34。C 同时给出左右边界辅助函数；比较两个函数中的等号，理解首个 ≥ 与首个 > 的差别。

模板 A · 精确命中（闭区间）

Python 3 · 通用模板 A

from typing import List

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums) - 1
        while left <= right:
            mid = left + (right - left) // 2
            if nums[mid] == target:
                return mid
            if nums[mid] < target:
                left = mid + 1
            else:
                right = mid - 1
        return -1

模板 B · 第一个大于等于 target

Python 3 · 通用模板 B

from typing import List

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

模板 C · 第一个严格大于 target

Python 3 · 通用模板 C

from typing import List

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        first = self.lower_bound(nums, target)
        end = self.upper_bound(nums, target)
        if first == end:
            return [-1, -1]
        return [first, end - 1]

    def lower_bound(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums)
        while left < right:
            mid = left + (right - left) // 2
            if nums[mid] < target:
                left = mid + 1
            else:
                right = mid
        return left

    def upper_bound(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums)
        while left < right:
            mid = left + (right - left) // 2
            if nums[mid] <= target:
                left = mid + 1
            else:
                right = mid
        return left

三个模板均为 O(log(n+1)) 时间、O(1) 空间。B、C 仅差一个等号，但分别对应两条不同的单调判定。B 的不变量：下标 <left 的元素均 <target，下标 ≥right 的元素均 ≥target；C 将两侧条件改成 ≤target 与 >target。

想求的边界	公式（L=lower_bound，R=upper_bound）	缺失时注意
第一个 ≥t	L(t)	可能等于 n
第一个 >t	R(t)	可能等于 n
最后一个 <t	L(t)−1	可能等于 -1
最后一个 ≤t	R(t)−1	可能等于 -1
等值段	[L(t),R(t)−1]	必须检查 L<n 且 nums[L]==t
等值个数	R(t)−L(t)	缺失时为 0

动手推演：等于目标时为什么继续向左？

数组 [5,7,7,8,8,10]，target=8；寻找第一个 ≥8 的下标。蓝色是待分类候选，金色标出本轮中点，淡色区域已完成分类。

可对照第 34 题的完整推演。终止 left=right=3，答案下标为 3，值为 8。

STAGE 01 / 05

第 1 阶段 · 基础模板

从精确命中走向插入边界

01LeetCode 704二分查找

LeetCode 原题 ↗

难度：简单｜核心知识点：闭区间、左闭右开区间、循环不变量

题意与约束

在严格递增、无重复的整数数组 nums 中寻找 target，存在返回下标，否则返回 -1。原题数组非空，要求 O(log n)；两种实现也支持空数组。

解法一：闭区间精确查找（推荐起点）

维护仍可能包含目标的闭区间 [left,right]。中点偏小时排除左半边，偏大时排除右半边；相等即可返回。

Python 3 · 可直接提交

from typing import List

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums) - 1
        while left <= right:
            mid = left + (right - left) // 2
            if nums[mid] == target:
                return mid
            if nums[mid] < target:
                left = mid + 1
            else:
                right = mid - 1
        return -1

关键代码解释

right=n-1 是有效下标。left≤right 保证剩一个元素也会检查。
中点检查过后，用 mid+1 或 mid-1 将其排除，候选范围严格缩小。

示例推演

轮次	left,right	mid / 值	决策：[-1,0,3,5,9,12]，target=9
1	0,5	2 / 3	3<9 → left=3
2	3,5	4 / 9	命中，返回 4

正确性：每次排除的元素均不等于目标，退出时 left>right，所有候选已检查或被排除。

时间复杂度 O(log(n+1))，非空时通常写 O(log n)。空间复杂度 O(1)。

解法二：左闭右开精确查找

候选元素改为 [left,right)，右端点不包含在内。中点偏大时设置 right=mid，便排除了中点与右侧。

Python 3 · 可直接提交

from typing import List

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums)
        while left < right:
            mid = left + (right - left) // 2
            if nums[mid] == target:
                return mid
            if nums[mid] < target:
                left = mid + 1
            else:
                right = mid
        return -1

关键代码解释

right=n 是边界而不是待访问元素；left<right 保证 mid<n。
right=mid 必须与左闭右开定义配套，不能换成 mid-1。

示例推演

轮次	[left,right)	mid / 值	决策：[-1,0,3,5,9,12]，target=2
1	[0,6)	3 / 5	right=3
2	[0,3)	1 / 0	left=2
3	[2,3)	2 / 3	right=2，空区间，返回 -1

正确性：所有可能位置都保留在候选区间；left=right 时候选为空，说明不存在。

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

解法比较与选择

写法	优势	退出状态
闭区间	精确查找含义直观	left>right
左闭右开	便于迁移 lower_bound	left=right

边界用例

输入 / 场景	预期结果
[-1,0,3,5,9,12], target=9 / 2	4 / -1
[1], target=1 / 0	0 / -1
[]（扩展）	-1

易错点

不要把 right=n 与 while left≤right 混用，否则可能访问 nums[n]。
找到一个等值下标，不等于找到重复段的最左下标。
Python 整数不会固定宽度溢出；差值中点写法方便迁移其他语言。

02LeetCode 35搜索插入位置

LeetCode 原题 ↗

难度：简单｜核心知识点：lower_bound、插入点、虚拟哨兵

题意与约束

给定无重复的升序数组和目标值，返回目标下标；不存在则返回保持升序的插入下标，允许为 n。只计算位置，不真正插入，要求 O(log n)。原题数组非空。

解法一：第一个大于等于 target 的位置

把问题统一成 lower_bound：寻找第一个满足 nums[i]≥target 的位置。相等时继续向左收缩。left 左侧已知都小于目标，right 开始已知都大于等于目标。

Python 3 · 可直接提交

from typing import List

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

关键代码解释

只有 nums[mid]<target 才能排除中点和左侧。
相等时 right=mid，保留 mid 作为潜在边界。
返回值属于 [0,n]；所有元素都更小时得到虚拟位置 n，不能直接访问 nums[n]。

示例推演

轮次	[left,right)	mid / 值	决策：[1,3,5,6]，target=2
1	[0,4)	2 / 5	right=2
2	[0,2)	1 / 3	right=1
3	[0,1)	0 / 1	left=1，返回 1

正确性：终止时 left 左边全小于 target，而 left 开始全大于等于 target，所以 left 就是插入点。

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

解法二：标准库 bisect_left

标准库直接返回左侧插入点。工程中简洁可靠；面试时仍应解释 lower_bound 的分割规则并能够手写。

Python 3 · 可直接提交

from typing import List
from bisect import bisect_left

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

关键代码解释

bisect_left 只查位置，不改变原数组。
不要改用 insort；实际插入移动元素，通常耗时 O(n)。

示例推演

数组	target	返回 / 含义
[1,3,5,6]	5	2，现有下标
[1,3,5,6]	7	4，尾部插入
[1,3,5,6]	0	0，头部插入

正确性：库函数保证返回位置左边均小于目标，右边均大于等于目标，恰好符合插入语义。

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

解法比较与选择

方法	建议
手写 lower_bound	学习和面试必须掌握
bisect_left	工程实现简洁，但须讲明语义

边界用例

输入 / 场景	预期结果
[1,3,5,6], target=5 / 2 / 7	2 / 1 / 4
[1], target=0 / 1 / 2	0 / 0 / 1
[]（扩展）	0

易错点

不存在也必须返回插入位置，而非 -1。
相等即返回只适用于本题的无重复条件，不能作为通用左边界模板。
查找为 O(log n)，执行数组插入为 O(n)，不要混淆。

STAGE 02 / 05

第 2 阶段 · 边界与答案

重复段与数值可行性

03LeetCode 34在排序数组中查找元素的第一个和最后一个位置

LeetCode 原题 ↗

难度：中等｜核心知识点：重复段、lower_bound、upper_bound

题意与约束

在非递减数组中返回 target 的首尾下标，缺失返回 [-1,-1]。数组允许为空、允许重复，要求 O(log n)，不能在线性扩展重复段后仍称对数复杂度。

解法一：两次边界二分（推荐）

等值元素连续出现。寻找第一个 ≥target 的位置 L 与第一个 >target 的位置 R，存在时返回 [L,R−1]。两次二分均不扫描重复段。

Python 3 · 可直接提交

from typing import List

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        def boundary(strict: bool) -> int:
            left, right = 0, len(nums)
            while left < right:
                mid = left + (right - left) // 2
                if nums[mid] < target or (strict and nums[mid] == target):
                    left = mid + 1
                else:
                    right = mid
            return left

        first = boundary(False)  # 第一个 >= target
        if first == len(nums) or nums[first] != target:
            return [-1, -1]
        last = boundary(True) - 1  # 第一个 > target 减一
        return [first, last]

关键代码解释

strict=False 时相等归右侧，得到 lower_bound。
strict=True 时相等也向右走，越过所有等值元素，得到 upper_bound。
先检查 first==n，利用 or 短路避免越界；再确认 nums[first]==target。

示例推演

边界	left,right → mid	判定 / 更新：[5,7,7,8,8,10]，target=8
L	0,6 → 3	8≥8 → right=3
L	0,3 → 1；2,3 → 2	7<8 → left=2；7<8 → left=3，L=3
R	0,6 → 3	8≤8 → left=4
R	4,6 → 5；4,5 → 4	10>8 → right=5；8≤8 → left=5，R=5
结果	[L,R−1]	[3,4]

正确性：L 前均小于目标，R 开始均大于目标，夹住的元素恰好全等于目标。存在性检查排除了空段。

时间复杂度 O(log(n+1))，两次对数搜索仍为对数级。空间复杂度 O(1)。

解法二：bisect_left + bisect_right

用库函数返回左右插入点。右插入点在等值段之后，必须减一才能得到最后一个等值下标。

Python 3 · 可直接提交

from typing import List
from bisect import bisect_left, bisect_right

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        first = bisect_left(nums, target)
        if first == len(nums) or nums[first] != target:
            return [-1, -1]
        return [first, bisect_right(nums, target) - 1]

关键代码解释

bisect_right 返回第一个 >target 的下标，不是最后一个等值下标。
库函数只计算插入点，不保证元素存在，仍需检查。

示例推演

输入	L / R	结果
[5,7,7,8,8,10], 8	3 / 5	[3,4]
[5,7,7,8,8,10], 6	1 / 1	nums[1]≠6，返回 [-1,-1]
[], 0	0 / 0	first==n，返回 [-1,-1]

正确性：库函数两种分割规则分别对应两条边界，存在性校验保证最终区间有实际目标。

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

解法比较与选择

方法	优势	需要注意
手写两边界	体现等号处理与不变量	解释 strict 改变的判定
bisect 双边界	短小可靠	存在性检查不可省略

边界用例

输入 / 场景	预期结果
[5,7,7,8,8,10], target=8 / 6	[3,4] / [-1,-1]
[], target=0	[-1,-1]
[2,2,2], target=2	[0,2]
[1], target=0 / 1 / 2	[-1,-1] / [0,0] / [-1,-1]

易错点

相等就返回无法定位首尾；向两侧扫描在全相等输入下退化到 O(n)。
最后位置是 upper_bound(target)-1，不是 lower_bound(target)-1。
对整数可用 lower_bound(target+1) 求 R，但直接写严格大于更通用，也避免迁移语言时 target+1 溢出。

04LeetCode 69x 的平方根

LeetCode 原题 ↗

难度：简单｜核心知识点：二分答案、最后一个可行值、整数牛顿迭代

题意与约束

给定 0≤x≤2³¹−1，返回非负平方根的整数部分，即最大的整数 a，使 a²≤x。不可使用内置开方、pow(x,0.5) 或 x**0.5，结果需向下取整。

解法一：二分答案，保留最后一个可行值

在数值域 [0,x] 中搜索。判定 a²≤x 呈现“真…真、假…假”，因此求最后一个真：可行时记录，再向右尝试；不可行时向左收缩。无需构造候选数组。

Python 3 · 可直接提交

class Solution:
    def mySqrt(self, x: int) -> int:
        left, right = 0, x
        answer = 0
        while left <= right:
            mid = left + (right - left) // 2
            if mid * mid <= x:
                answer = mid
                left = mid + 1
            else:
                right = mid - 1
        return answer

关键代码解释

answer 只保存已验证可行的值。
可行不代表最大，left=mid+1 继续寻找更大的可行值。
Python 乘法无固定宽度溢出；其他语言可考虑 mid≤x//mid，但要单独处理 mid=0。

示例推演

轮次	left,right	mid / 平方	更新：x=8
1	0,8	4 / 16	right=3
2	0,3	1 / 1	answer=1，left=2
3	2,3	2 / 4	answer=2，left=3
4	3,3	3 / 9	right=2，退出返回 2

正确性：最大可行值始终是已记录答案或剩余候选；退出后所有候选已排除，answer 满足 a²≤x<(a+1)²。

时间复杂度 O(log(x+1))，x=0 时常数时间。空间复杂度 O(1)。

解法二：整数牛顿迭代（进阶补充）

对 g²−x=0 使用牛顿更新 g←(g+x/g)/2，并用整数除法实现。从 x 起步，由答案上方向下逼近，停止时即为 floor(√x)。

Python 3 · 可直接提交

class Solution:
    def mySqrt(self, x: int) -> int:
        if x < 2:
            return x
        guess = x
        while guess * guess > x:
            guess = (guess + x // guess) // 2
        return guess

关键代码解释

x<2 时直接返回，避免 x=0 除零。
guess²>x 时 x//guess<guess，所以每次整数更新严格减小。
用平方判断停止，无需浮点误差阈值。

示例推演

步骤	guess	检查：x=8
初始	8	64>8
1	(8+1)//2=4	16>8
2	(4+2)//2=3	9>8
3	(3+2)//2=2	4≤8，返回 2

正确性：令 k=floor(√x)。对 g≥k+1，由 g+x/g≥2√x≥2k，整数更新仍≥k；且 g²>x 时严格下降，最终只能在 k 停止。

时间复杂度 O(log(x+1)) 次迭代的上界；从 x 起步，接近根时收敛更快。空间复杂度 O(1)。

解法比较与选择

方法	优点	建议
二分答案	稳健、易证、能迁移单调判定	必须掌握
整数牛顿	实际迭代常较少	理解取整和下降证明后再用

边界用例

输入 / 场景	预期结果
x=0 / 1 / 4 / 8	0 / 1 / 2 / 2
x=2147395600	46340
x=2147483647	46340

易错点

必须向下取整，x=8 返回 2，不能四舍五入。
int(x**0.5) 违反题目限制，也不适合作为精确整数算法。
闭区间中若写 left=mid，可能不收缩而死循环。
复杂度采用 LeetCode 常见整数操作模型；任意精度大整数时需另计乘除法位复杂度。

STAGE 03 / 05

第 3 阶段 · 矩阵应用

先确认有序条件，再选择搜索方法

05LeetCode 74搜索二维矩阵

LeetCode 原题 ↗

难度：中等｜核心知识点：虚拟展平、下标映射、两次二分

题意与约束

m×n 矩阵每行非递减，后一行首元素严格大于前一行末元素。判断 target 是否出现，要求 O(log(mn))。原题 m,n≥1；实现额外防御空矩阵、首行为空的情况。

虚拟展平：只转换下标，不复制矩阵。

解法一：虚拟一维数组二分（推荐）

跨行条件保证按行读取的整个序列有序，把 [0,mn−1] 当作下标域，只在访问中点时转换成行列坐标。

Python 3 · 可直接提交

from typing import List

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        if not matrix or not matrix[0]:
            return False
        rows, cols = len(matrix), len(matrix[0])
        left, right = 0, rows * cols - 1
        while left <= right:
            mid = left + (right - left) // 2
            value = matrix[mid // cols][mid % cols]
            if value == target:
                return True
            if value < target:
                left = mid + 1
            else:
                right = mid - 1
        return False

关键代码解释

mid//cols 是行号，mid%cols 是列号；除数必须为列数。
先检查空输入，再访问 matrix[0]。
不能真实展平：那样会额外消耗 O(mn) 时间与空间。

示例推演

轮次	left,right	mid → 坐标 / 值	决策：图中矩阵，target=3
1	0,11	5 → (1,1) / 11	right=4
2	0,4	2 → (0,2) / 5	right=1
3	0,1	0 → (0,0) / 1	left=1
4	1,1	1 → (0,1) / 3	命中 True

正确性：映射与按行序列一一对应，该序列有序，因此普通二分不会排除可能的目标。

时间复杂度 O(log(mn+1))，通常写 O(log(mn))。空间复杂度 O(1)。

解法二：先定位行，再二分列

在行首序列中找第一个 >target 的位置，减一得到最后一个行首≤target 的候选行，再在其中精确二分。跨行严格分离保证其他行均不可能命中。

Python 3 · 可直接提交

from typing import List

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        if not matrix or not matrix[0]:
            return False
        left, right = 0, len(matrix)
        while left < right:
            mid = left + (right - left) // 2
            if matrix[mid][0] <= target:
                left = mid + 1
            else:
                right = mid
        row = left - 1
        if row < 0:
            return False
        left, right = 0, len(matrix[0]) - 1
        while left <= right:
            mid = left + (right - left) // 2
            value = matrix[row][mid]
            if value == target:
                return True
            if value < target:
                left = mid + 1
            else:
                right = mid - 1
        return False

关键代码解释

row=left-1 可能为 -1，需显式检查，避免 Python 负索引访问最后一行。
直接比较 matrix[mid][0]，不创建行首数组，保持常数空间。
第一轮求插入边界，第二轮求精确命中，退出语义不同。

示例推演

阶段	关键状态	结果：图中矩阵，target=13
行首二分	mid=1：10≤13 → left=2；mid=2：23>13 → right=2	row=1
行内二分	mid=1：11 偏小；mid=2：16 偏大	区间为空，返回 False

正确性：候选行之前的值均小于候选行首，候选行之后的行首大于 target；唯一可能行内再做二分即可。

时间复杂度 O(log(m+1)+log(n+1))，有效非空时与 O(log(mn)) 同阶。空间复杂度 O(1)。

解法比较与选择

方法	优势	代价
虚拟展平	代码紧凑，一轮搜索	记住行列映射
先行后列	结构清楚，定位直观	两轮边界语义不同

边界用例

输入 / 场景	预期结果
图中矩阵，target=3 / 13	True / False
[[1]], target=1 / 0	True / False
[[1],[3],[5]], target=3	True
[] / [[]]（扩展）	False

易错点

第 240 题只保证行列分别有序，不能直接展平。
一行多列、一列多行均需使用 cols 做映射。
真实展平或排序后的预处理复杂度不能忽略。

06LeetCode 240搜索二维矩阵 II

LeetCode 原题 ↗

难度：中等｜核心知识点：行列双单调、阶梯搜索、逐行二分

题意与约束

矩阵每行从左到右有序，每列从上到下有序，判断目标是否存在。不保证后一行首元素大于前一行末元素，所以按行展平可能无序。原题 m,n≥1。

target=5：15 → 11 → 7 → 4 ↓ 5。偏大删列，偏小删行。

解法一：右上角阶梯搜索（通常优先）

从右上角开始，左边更小、下边更大。当前值偏大时，该列下方也偏大，删除整列；偏小时，该行左侧也偏小，删除整行。这是单调搜索，并非每次减半的二分。

Python 3 · 可直接提交

from typing import List

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        if not matrix or not matrix[0]:
            return False
        row, col = 0, len(matrix[0]) - 1
        while row < len(matrix) and col >= 0:
            value = matrix[row][col]
            if value == target:
                return True
            if value > target:
                col -= 1
            else:
                row += 1
        return False

关键代码解释

value>target：col-=1，排除当前候选列。
value<target：row+=1，排除当前候选行。
左上角右方和下方都更大，偏小时无法唯一决定排除方向；也可对称地从左下角开始。

示例推演

步骤	坐标 / 值	更新：图中矩阵，target=5
1	(0,4) / 15	col=3
2	(0,3) / 11	col=2
3	(0,2) / 7	col=1
4	(0,1) / 4	row=1
5	(1,1) / 5	返回 True

正确性：候选矩形为行 row…m−1、列 0…col，每步删除的整行或整列均不含目标，越界时候选为空。

时间复杂度 O(m+n)，最多比较 m+n−1 个位置。空间复杂度 O(1)。

解法二：逐行二分（保留二分视角）

每一行有序，可分别二分。若行首大于目标，第一列单调意味着后续行也不可能命中；若行尾小于目标，仅跳过当前行。

Python 3 · 可直接提交

from typing import List

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        if not matrix or not matrix[0]:
            return False
        for row in matrix:
            if target < row[0]:
                break
            if target > row[-1]:
                continue
            left, right = 0, len(row) - 1
            while left <= right:
                mid = left + (right - left) // 2
                if row[mid] == target:
                    return True
                if row[mid] < target:
                    left = mid + 1
                else:
                    right = mid - 1
        return False

关键代码解释

target<row[0] 可 break，依赖列方向有序。
target>row[-1] 只能 continue，后续行仍可能出现目标。
不切片、不拷贝，row 只是当前行的引用。

示例推演

行	二分过程	结果：图中矩阵，target=5
第 0 行	mid=2 → 7；mid=0 → 1；mid=1 → 4	本行未找到
第 1 行	mid=2 → 8；mid=0 → 2；mid=1 → 5	返回 True

正确性：行内二分覆盖每行可能位置，剪枝排除的行也均不含目标，所以不会遗漏。

时间复杂度 O(m log(n+1))；对称逐列法为 O(n log(m+1))。空间复杂度 O(1)。

解法比较与选择

方法	时间	选择依据
阶梯搜索	O(m+n)	维度相近时通常优先
逐行二分	O(m log(n+1))	行少列多
逐列二分（对称变形）	O(n log(m+1))	列少行多

边界用例

输入 / 场景	预期结果
图中矩阵，target=5 / 20	True / False
[[1,4],[2,5]], target=2	True
[[1,3,5]], target=4	False
[[1],[3],[5]], target=3	True
[] / [[]]（扩展）	False

易错点

[[1,4],[2,5]] 展平为 [1,4,2,5]，这是误用第 74 题算法的反例。
阶梯法 O(m+n) 不等于 O(log(mn))。
m=1、n 很大时逐行二分更合适，不能笼统断言阶梯法总更优。

STAGE 04 / 05

第 4 阶段 · 旋转数组

先找断点，再识别有序半边

07LeetCode 153寻找旋转排序数组中的最小值

LeetCode 原题 ↗

难度：中等｜核心知识点：局部有序、保留中点、收敛区间

题意与约束

无重复的升序数组旋转后，返回最小元素，要求 O(log n)。旋转整圈可回到原数组；原题保证非空。返回元素值而非下标。

[4,5,6,7,0,1,2] 只有一个下降断点，最小值 0 的下标为 4。

解法：比较 mid 与 right，保留可能答案

维护最小值一定在 [left,right]。若 nums[mid]>nums[right]，中点位于较大段，最小值严格在右边；否则 mid…right 已有序，最小值在左半边且可能就是 mid。

Python 3 · 可直接提交

from typing import List

class Solution:
    def findMin(self, nums: List[int]) -> int:
        left, right = 0, len(nums) - 1
        while left < right:
            mid = left + (right - left) // 2
            if nums[mid] > nums[right]:
                left = mid + 1
            else:
                right = mid
        return nums[left]

关键代码解释

left<right：剩一个候选便可返回，不必再验证。
right=mid 必须保留中点，例如 [3,1,2] 的 mid 正是最小值。
left<right 时下取整使 mid<right；无重复条件保证比较值不会相等。

示例推演

轮次	left,right	mid / 比较	更新：[4,5,6,7,0,1,2]
1	0,6	3 / 7>2	left=4
2	4,6	5 / 1<2	right=5
3	4,5	4 / 0<1	right=4；返回 nums[4]=0

正确性：每次保留最小值所在区间，且候选长度严格下降；终止时唯一候选即答案。

时间复杂度 O(log n)，n=1 时常数时间。空间复杂度 O(1)。

边界用例

输入 / 场景	预期结果
[3,4,5,1,2]	1
[4,5,6,7,0,1,2]	0
[11,13,15,17]	11
[1] / [2,1] / [1,2]	1 / 1 / 1

易错点

第二个分支不能写 right=mid-1，否则会删除最小值。
比较 nums[mid] 与 nums[0] 的其他写法需额外处理未旋转情况。
本题无重复；有重复时相等可能无法判边，保守 right-=1 的最坏时间可达 O(n)。
原题没有空数组，不为 [] 编造最小值。

08LeetCode 33搜索旋转排序数组

LeetCode 原题 ↗

难度：中等｜核心知识点：有序半边、区间归属、旋转点

题意与约束

无重复升序数组旋转后，在其中查找 target，存在返回当前数组下标，否则返回 -1，要求 O(log n)。不能先排序，排序既丢失原下标，又超过目标复杂度。

解法一：每次识别有序半边（推荐）

只有一个下降断点，中点两边至少一半有序。先确定有序半边，再检查 target 是否属于该半边值域；属于便保留它，否则保留另一边。

Python 3 · 可直接提交

from typing import List

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums) - 1
        while left <= right:
            mid = left + (right - left) // 2
            if nums[mid] == target:
                return mid
            if nums[left] <= nums[mid]:
                if nums[left] <= target < nums[mid]:
                    right = mid - 1
                else:
                    left = mid + 1
            else:
                if nums[mid] < target <= nums[right]:
                    left = mid + 1
                else:
                    right = mid - 1
        return -1

关键代码解释

先比较相等，后面所有分支都可排除 mid。
nums[left]≤nums[mid] 必须含等号，包含 left==mid 的两元素情况。
左值域为 nums[left]≤target<nums[mid]；右值域为 nums[mid]<target≤nums[right]，外端点要包含。

示例推演

轮次	left,right / mid	判定	更新：[4,5,6,7,0,1,2]，target=0
1	0,6 / 3	左 [4,5,6,7] 有序，0 不在 [4,7)	left=4
2	4,6 / 5	左 [0,1] 有序，0 在 [0,1)	right=4
3	4,4 / 4	nums[4]=0	返回 4

正确性：无重复保证有序半边的值域与另一段不混淆，每次排除不可能包含目标的一半，候选规模近似减半。

时间复杂度 O(log(n+1))，原题非空时通常写 O(log n)。空间复杂度 O(1)。

解法二：先找旋转点，再普通二分

先找到最小值下标 pivot，将数组分为两个递增段，再按目标值域选择其中一段精确二分。两轮代码均完整给出，可以独立提交。

Python 3 · 可直接提交

from typing import List

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        if not nums:
            return -1
        left, right = 0, len(nums) - 1
        while left < right:
            mid = left + (right - left) // 2
            if nums[mid] > nums[right]:
                left = mid + 1
            else:
                right = mid
        pivot = left

        if nums[pivot] <= target <= nums[-1]:
            left, right = pivot, len(nums) - 1
        else:
            left, right = 0, pivot - 1
        while left <= right:
            mid = left + (right - left) // 2
            if nums[mid] == target:
                return mid
            if nums[mid] < target:
                left = mid + 1
            else:
                right = mid - 1
        return -1

关键代码解释

pivot 为最小值下标，未旋转时为 0。
目标落在 [nums[pivot],nums[-1]] 内时选右段，否则选左段。
始终使用原数组下标，不切片，因此无须补偏移，也不增加空间。

示例推演

阶段	关键状态：[4,5,6,7,0,1,2]，target=0	结果
找旋转点	[0,6]→[4,6]→[4,5]→[4,4]	pivot=4
选段	0 在 [0,2] 内	搜索 [4,6]
精确二分	mid=5 值1偏大；mid=4 值0命中	返回 4

正确性：旋转点把数组分成两个有序且值域不交叠的段，目标只可能属于选中的段，普通二分即可完成判断。

时间复杂度 O(log n)+O(log n)=O(log n)；空输入常数时间。空间复杂度 O(1)。

解法比较与选择

方法	优点	注意
判断有序半边	一轮循环，通常比较更少	值域四个边界要准确
先旋转点后查找	结构清楚，可复用最小值思路	两轮二分，避免切片

边界用例

输入 / 场景	预期结果
[4,5,6,7,0,1,2], target=0 / 3	4 / -1
[1], target=0 / 1	-1 / 0
[3,1], target=1	1
[1,2,3], target=3	2
[]（扩展）	-1

易错点

不能只比较 target 与 nums[mid]，整个数组并非全局有序。
有序半边判定必须含等号；[3,1]、target=1 是很好的反例。
求最小值时可能保留 mid，精确搜索排除 mid，两者更新规则不能混用。
无重复是对数复杂度保证的关键；允许重复需要另做判定。

STAGE 05 / 05

第 5 阶段 · 进阶划分

把中位数转化为满足约束的切口

09LeetCode 4寻找两个正序数组的中位数

LeetCode 原题 ↗

难度：困难｜核心知识点：切分二分、左右有序、哨兵、第 k 小

题意与约束

给定两个分别有序、允许重复的数组 nums1、nums2，返回合并后的中位数。可以有一个数组为空，但总长度至少为 1。要求 O(log(m+n))，且不修改输入。先用归并理解定义，再掌握两种对数算法。

总长度为奇数时取第 (m+n+1)//2 小；偶数时取第 (m+n)//2 与下一位的平均数。下标从 0 开始，而“第 k 小”的排名从 1 开始。

A=[1,2]，B=[3,4]，i=2、j=0。哨兵表示空侧，非实际元素；中位数=(2+3)/2。

解法一：在较短数组上二分切分（推荐提交）

在 A 中取 i 个元素放左边，在 B 中取 j=half−i 个元素放左边，使左侧总数固定。每个数组内部已经有序，只需满足两条交叉条件：A_left≤B_right 且 B_left≤A_right。若 A_left>B_right，A 左边取多了，将 i 左移；反之 B_left>A_right，将 i 右移。

Python 3 · 可直接提交

from typing import List

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        a, b = nums1, nums2
        if len(a) > len(b):
            a, b = b, a
        m, n = len(a), len(b)
        half = (m + n + 1) // 2
        left, right = 0, m
        while left <= right:
            i = left + (right - left) // 2
            j = half - i
            a_left = a[i - 1] if i > 0 else float('-inf')
            a_right = a[i] if i < m else float('inf')
            b_left = b[j - 1] if j > 0 else float('-inf')
            b_right = b[j] if j < n else float('inf')
            if a_left <= b_right and b_left <= a_right:
                if (m + n) % 2:
                    return float(max(a_left, b_left))
                return (max(a_left, b_left) + min(a_right, b_right)) / 2
            if a_left > b_right:
                right = i - 1
            else:
                left = i + 1
        raise ValueError('输入必须为有序数组且总长度至少为 1')

关键代码解释

先让 m≤n，确保任意 i∈[0,m] 时 0≤j≤n，避免访问 B 越界。
half=(m+n+1)//2 使奇数总长度时左侧多一个，答案就是左侧最大。
i=0 或 j=0 用 −∞，i=m 或 j=n 用 +∞；先判断边界再访问，避免负索引误读。
偶数时取左侧最大与右侧最小的平均，用 / 而不是 //。
最后的 raise 只是防御路径，不会在合法输入上触发，也不等同于完整的输入排序验证。

示例推演

轮次	i / j	A_left, A_right	B_left, B_right	决策：A=[1,2]，B=[3,4]
1	1 / 1	1, 2	3, 4	B_left=3>2，i 太小 → left=2
2	2 / 0	2, +∞	−∞, 3	两条件成立 → (2+3)/2=2.5
奇数补例 1	0 / 2	−∞, 2	3, +∞	A=[2]，B=[1,3]；3>2，left=1
奇数补例 2	1 / 1	2, +∞	1, 3	合法，左侧 [1,2]，返回 2.0

正确性：左侧元素数已固定，且两个数组各自有序；两条交叉条件使所有左值≤所有右值，故中间边界即中位数。切口过大或过小可单调排除，所以二分有效。

时间复杂度 O(log(min(m,n)+1))，满足 O(log(m+n))；短数组为空时常数时间。空间复杂度 O(1)，交换引用，不复制数组。

解法二：不断排除前缀，寻找第 k 小

在两个剩余后缀中各看至多 k//2 个元素的末尾，排除末尾值较小的那段前缀，并扣减排名。无需合并或切片。某个数组耗尽时，答案就是另一个数组中的偏移元素。

Python 3 · 可直接提交

from typing import List

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        def kth(k: int) -> int:
            i = j = 0
            while True:
                if i == len(nums1):
                    return nums2[j + k - 1]
                if j == len(nums2):
                    return nums1[i + k - 1]
                if k == 1:
                    return min(nums1[i], nums2[j])
                half = k // 2
                ni = min(i + half, len(nums1)) - 1
                nj = min(j + half, len(nums2)) - 1
                if nums1[ni] <= nums2[nj]:
                    removed = ni - i + 1
                    i = ni + 1
                else:
                    removed = nj - j + 1
                    j = nj + 1
                k -= removed

        total = len(nums1) + len(nums2)
        if total % 2:
            return float(kth(total // 2 + 1))
        return (kth(total // 2) + kth(total // 2 + 1)) / 2

关键代码解释

k 是剩余序列中的 1 起始排名，不能误用为 0 起始下标。
ni、nj 用 min 截断，删除数量必须是实际长度，不能始终减 half。
先处理数组耗尽，再读 nums1[i]、nums2[j]，避免单数组为空时越界。
偶数时两次 kth 都从 i=j=0 开始，二者互不影响。

示例推演

步骤	剩余数组 / k	比较与删除	结果：A=[1,2]，B=[3,4]
找第2小	[1,2]、[3,4]，k=2	1≤3，删 A 的 1，k=1	min(2,3)=2
找第3小	[1,2]、[3,4]，k=3	1≤3，删 1，k=2；2≤3，再删 2，k=1	A 耗尽，返回 B[0]=3
组合	2 与 3	(2+3)/2	2.5

正确性：较小探针之前的 p 个元素可放在第 k 个之前：另一探针前至多 q−1 个更小值，p+q−1<k。相等时按稳定次序处理也能安全删除较小探针所在前缀。扣减 k 后问题等价。

时间复杂度 O(log(m+n))；每步删除约 k/2 个元素，截断后若未删足则一侧耗尽并立即结束。空间复杂度 O(1)，迭代且不切片。

解法三：双指针归并到中点（理解用，不满足对数要求）

像归并排序的合并步骤一样，每次取两个未消费首元素中的较小值，只走到中间位置。保留最近两个值即可算中位数，不需要保存整个合并数组。它帮助理解问题，但不满足原题要求的对数时间。

Python 3 · 可直接提交

from typing import List

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        total = len(nums1) + len(nums2)
        i = j = 0
        previous = current = 0
        for _ in range(total // 2 + 1):
            previous = current
            if i < len(nums1) and (j == len(nums2) or nums1[i] <= nums2[j]):
                current = nums1[i]
                i += 1
            else:
                current = nums2[j]
                j += 1
        if total % 2:
            return float(current)
        return (previous + current) / 2

关键代码解释

走 total//2+1 次，确保读到 0 起始下标 total//2。
previous 保留上一个值，current 保留当前值。
判断数组耗尽后再访问元素，利用 and/or 短路避免越界。

示例推演

步数	取出元素	previous / current	说明：A=[1,2]，B=[3,4]
1	1	0 / 1	previous 初值不参与最后结果
2	2	1 / 2	保存最近两项
3	3	2 / 3	返回 (2+3)/2=2.5

正确性：每步取两数组当前最小值，得到正确的有序前缀，走到中点即可得到中位数所需的一或两个值。

时间复杂度 O(m+n)，仅走一半仍为线性级；不符合本题对数要求。空间复杂度 O(1)，不构造合并结果。

解法比较与选择

解法	时间	额外空间	选择
切分二分	O(log(min(m,n)+1))	O(1)	首选，掌握切口与哨兵
第 k 小排除	O(log(m+n))	O(1)	迁移排名问题，注意实际删除数
归并到中点	O(m+n)	O(1)	解释基线，不满足对数要求

边界用例

输入 / 场景	预期结果
[1,3] 与 [2]	2.0
[1,2] 与 [3,4]	2.5
[] 与 [1]	1.0
[0,0] 与 [0,0]	0.0
[-5,-3] 与 [-4,-2]	-3.5
[1] 与 [2,3,4,5,6,7,8,9]	5.0

易错点

不要将两个有序数组直接拼接并排序当作最优解，时间为 O((m+n)log(m+n))。
切分中的 i 表示左侧取的元素个数，可等于 m；它不是始终有效的元素下标。
奇数时左侧多一个，返回 max(left)，偶数返回两侧边界平均。
总长度至少为 1；两个数组都空时中位数没有定义，不属于合法输入。
不能盲目移植含切片的递归 kth 代码后声称 O(1) 空间。

复盘 · 让模板成为判断能力

看到题目，先问哪一个条件成立？

结构 / 问题	选择	代表题
全局有序，找精确值	普通二分	704
插入点、重复段	lower_bound / upper_bound	35、34
数值越大越不可行	二分答案，找最后一个可行值	69
跨行严格分离	虚拟展平或先行后列	74
仅行列各自有序	阶梯搜索或逐行二分	240
无重复的旋转数组	比较右端点 / 识别有序半边	153、33
两个有序数组中间排名	切分平衡与交叉边界 / 第 k 小	4

九题知识点与复杂度总表

题号	推荐算法	时间	辅助空间
704	精确二分	O(log n)	O(1)
35	lower_bound	O(log n)	O(1)
34	双边界	O(log(n+1))	O(1)
69	二分答案	O(log(x+1))	O(1)
74	虚拟展平	O(log(mn))	O(1)
240	阶梯搜索	O(m+n)	O(1)
153	与右端点比较	O(log n)	O(1)
33	识别有序半边	O(log n)	O(1)
4	短数组切分	O(log(min(m,n)+1))	O(1)

面试表达：用这五句话组织答案

我利用的有序性 / 单调性是……；如果这个条件缺失，当前策略不能直接使用。
候选区间定义为……；循环不变量是……。
中点满足这个条件时，另一半不可能有答案，因为……。
区间每轮严格变小，退出时……就是所求边界 / 唯一候选。
时间为……，空间为……；我用空输入、单元素、两元素、缺失、重复和极值检查边界。

闭卷自测清单

解释闭区间、左闭右开和收敛区间的差异不看答案写出 lower_bound 与 upper_bound说明返回值 n 与 -1 何时是合法哨兵写出 a²≤x<(a+1)² 并证明平方根结果给出 74 可展平、240 不可展平的反例用 [3,1] 和 [3,1,2] 检查旋转题等号与中点推导 half、i、j 及两条交叉条件说明第 k 小每次实际删除多少元素

五天学习计划与间隔复习

安排	练习	验收目标
Day 1 · 60–90 分钟	基础知识、模板、704、35	独立写出两种区间和 lower_bound
Day 2 · 60–90 分钟	34、69	解释等号归属，检查零与最大输入
Day 3 · 60–90 分钟	74、240	根据矩阵约束选方法并画搜索轨迹
Day 4 · 60–90 分钟	153、33	解释保留中点与排除中点的区别
Day 5 · 90–120 分钟	4，随后混合闭卷练习	手写切分二分，用空侧和奇偶验证
完成后第 1 / 3 / 7 / 14 天	随机抽 2–3 题，限时复现	记下错误的不变量或边界，未独立写出则取消掌握标记

掌握标准：能够独立写出正确代码、解释每个等号、逐轮推演一个边界用例，并准确说明复杂度。记住答案下标通常在 0…n−1，而插入边界可在 0…n。

来源与离线说明

题号、题意条件与难度以各题卡片中的 LeetCode 原题页为准，核对日期：2026-10-27。教程、代码、推演与 SVG 图解均在本文件内。原题内容采用简述，完整题面请主动打开卡片链接查看。

学习进度、主题和自测清单保存在当前浏览器的 localStorage。请用同一个浏览器、同一路径打开；清除浏览器数据、移动文件或使用无痕窗口可能使进度不同。若浏览器禁止本地存储，页面会提示，阅读和本次会话交互仍可使用。

二分查找从区间不变量，到中位数划分

建议的学习顺序

基础知识：二分的前提是可排除性

三种区间约定对照

核心模板：把边界统一成单调判定

模板 A · 精确命中（闭区间）

模板 B · 第一个大于等于 target

模板 C · 第一个严格大于 target

动手推演：等于目标时为什么继续向左？

01LeetCode 704二分查找

题意与约束

解法一：闭区间精确查找（推荐起点）

关键代码解释

示例推演

解法二：左闭右开精确查找

关键代码解释

示例推演

解法比较与选择

边界用例

易错点

02LeetCode 35搜索插入位置

题意与约束

解法一：第一个大于等于 target 的位置

关键代码解释

示例推演

解法二：标准库 bisect_left

关键代码解释

示例推演

解法比较与选择

边界用例

易错点

03LeetCode 34在排序数组中查找元素的第一个和最后一个位置

题意与约束

解法一：两次边界二分（推荐）

关键代码解释

示例推演

解法二：bisect_left + bisect_right

关键代码解释

示例推演

解法比较与选择

边界用例

易错点

04LeetCode 69x 的平方根

题意与约束

解法一：二分答案，保留最后一个可行值

关键代码解释

示例推演

解法二：整数牛顿迭代（进阶补充）

关键代码解释

示例推演

解法比较与选择

边界用例

易错点

05LeetCode 74搜索二维矩阵

题意与约束

解法一：虚拟一维数组二分（推荐）

关键代码解释

示例推演

解法二：先定位行，再二分列

关键代码解释

示例推演

解法比较与选择

边界用例

易错点

06LeetCode 240搜索二维矩阵 II

题意与约束

解法一：右上角阶梯搜索（通常优先）

关键代码解释

示例推演

解法二：逐行二分（保留二分视角）

关键代码解释

示例推演

解法比较与选择

边界用例

易错点

07LeetCode 153寻找旋转排序数组中的最小值

题意与约束

解法：比较 mid 与 right，保留可能答案

关键代码解释

示例推演

二分查找
从区间不变量，到中位数划分