二分查找 · Binary Search

一句话骨架：单调即可二分，关键是边界判定与 mid 是否纳入下一轮。

何时用

• 数组已排序或目标具有单调性（答案越大越容易满足 / 越小越容易满足）
• 在「找下标 / 找峰值 / 找第 K 个」这类需要 O(log n) 的场景
• 可以"猜答案 + 验证"的优化问题（如最小化最大值）

通用模板

left, right = 0, len(nums) - 1   # 闭区间 [left, right]
while left <= right:
    mid = (left + right) // 2
    if check(mid):
        right = mid - 1          # 答案在左半（含 mid 不满足时也走这分支）
    else:
        left = mid + 1
return left  # 第一个满足 check 的下标

边界三原则

1. 区间是「闭」还是「左闭右开」要从头到尾保持一致；
2. left = mid + 1 / right = mid - 1 必须保证搜索区间真的缩小，否则死循环；
3. 返回 left 还是 right 取决于「找第一个 / 最后一个满足条件」。

关卡 1 · 搜索旋转排序数组

学习目标

掌握"切开后至少有一半有序"这个 invariant——把不严格单调的数组也压回 O(log n)。这是二分思维从"前提单调"到"局部单调"的跃升。

#33搜索旋转排序数组中等

♥♥♥♥♥+0 XP🔥 0

0 / 12

📝 题目

整数数组 nums 按升序排列，数组中的值互不相同。在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标从 0 开始计数）。

给你旋转后的数组 nums 和一个整数 target，如果 nums 中存在这个目标值 target，则返回它的下标，否则返回 -1。

你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

示例 1

输入nums = [4,5,6,7,0,1,2], target = 0

输出4

示例 2

输入nums = [4,5,6,7,0,1,2], target = 3

输出-1

示例 3

输入nums = [1], target = 0

输出-1

约束

• 1 ≤ nums.length ≤ 5000
• -10⁴ ≤ nums[i], target ≤ 10⁴
• nums 中的每个值都独一无二
• nums 在某个未知下标处旋转

💡 思路：旋转数组虽然整体不有序，但每次取 mid 后，左半 [left, mid] 与右半 [mid, right] 中**至少有一半是有序的**。先判出哪一半有序，再判 target 是否落在该有序段的端点之间——是就走那一半（O(log n) 二分），否则走另一半。

✅ 完整解法

时间 O(log n) · 空间 O(1)

先把整段解法看懂，下面的选择题是对这段代码逐行的理解检验。

 1def search(nums: list[int], target: int) -> int: 2    left, right = 0, len(nums) - 1 3    while left <= right: 4        mid = (left + right) // 2 5        if nums[mid] == target: 6            return mid 7        # 判断左半 [left, mid] 是否有序 8        if nums[left] <= nums[mid]: 9            # 左半有序10            if nums[left] <= target < nums[mid]:11                right = mid - 112            else:13                left = mid + 114        else:15            # 右半 [mid, right] 有序16            if nums[mid] < target <= nums[right]:17                left = mid + 118            else:19                right = mid - 120    return -1

🐞 单步可视化

示例：nums = [4, 5, 6, 7, 0, 1, 2], target = 0

代码L2

 1def search(nums: list[int], target: int) -> int: 2    left, right = 0, len(nums) - 1 3    while left <= right: 4        mid = (left + right) // 2 5        if nums[mid] == target: 6            return mid 7        # 判断左半 [left, mid] 是否有序 8        if nums[left] <= nums[mid]: 9            # 左半有序10            if nums[left] <= target < nums[mid]:11                right = mid - 112            else:13                left = mid + 114        else:15            # 右半 [mid, right] 有序16            if nums[mid] < target <= nums[right]:17                left = mid + 118            else:19                right = mid - 120    return -1

数据流

target0L0R6

nums

0

4

L

1

5

2

6

3

7

4

0

5

1

6

2

R

1 / 9初始化 left=0, right=6

速度 慢中快

🧠 理解检验

每题都对应解法的某一行或某个决策

为什么不能直接对旋转后的 nums 跑普通二分？

mid 切开后，关于"哪一半有序"的关键 invariant 是？

判断"左半有序"的条件应该是？

 1def search(nums: list[int], target: int) -> int: 2    left, right = 0, len(nums) - 1 3    while left <= right: 4        mid = (left + right) // 2 5        if nums[mid] == target: 6            return mid 7        # 判断左半 [left, mid] 是否有序 8        if nums[left] <= nums[mid]: 9            # 左半有序10            if nums[left] <= target < nums[mid]:11                right = mid - 112            else:13                left = mid + 114        else:15            # 右半 [mid, right] 有序16            if nums[mid] < target <= nums[right]:17                left = mid + 118            else:19                right = mid - 120    return -1

左半有序时，target 在左半的判定区间应该是？

 1def search(nums: list[int], target: int) -> int: 2    left, right = 0, len(nums) - 1 3    while left <= right: 4        mid = (left + right) // 2 5        if nums[mid] == target: 6            return mid 7        # 判断左半 [left, mid] 是否有序 8        if nums[left] <= nums[mid]: 9            # 左半有序10            if nums[left] <= target < nums[mid]:11                right = mid - 112            else:13                left = mid + 114        else:15            # 右半 [mid, right] 有序16            if nums[mid] < target <= nums[right]:17                left = mid + 118            else:19                right = mid - 120    return -1

右半有序时，target 在右半的判定区间应该是？

 1def search(nums: list[int], target: int) -> int: 2    left, right = 0, len(nums) - 1 3    while left <= right: 4        mid = (left + right) // 2 5        if nums[mid] == target: 6            return mid 7        # 判断左半 [left, mid] 是否有序 8        if nums[left] <= nums[mid]: 9            # 左半有序10            if nums[left] <= target < nums[mid]:11                right = mid - 112            else:13                left = mid + 114        else:15            # 右半 [mid, right] 有序16            if nums[mid] < target <= nums[right]:17                left = mid + 118            else:19                right = mid - 120    return -1

Python 里 nums[left] <= target < nums[mid] 这种写法叫什么？

mid 用 (left + right) // 2 在大整数语言里要担心溢出，Python 里呢？

 1def search(nums: list[int], target: int) -> int: 2    left, right = 0, len(nums) - 1 3    while left <= right: 4        mid = (left + right) // 2 5        if nums[mid] == target: 6            return mid 7        # 判断左半 [left, mid] 是否有序 8        if nums[left] <= nums[mid]: 9            # 左半有序10            if nums[left] <= target < nums[mid]:11                right = mid - 112            else:13                left = mid + 114        else:15            # 右半 [mid, right] 有序16            if nums[mid] < target <= nums[right]:17                left = mid + 118            else:19                right = mid - 120    return -1

循环条件 while left <= right 与 while left < right 哪个对？

 1def search(nums: list[int], target: int) -> int: 2    left, right = 0, len(nums) - 1 3    while left <= right: 4        mid = (left + right) // 2 5        if nums[mid] == target: 6            return mid 7        # 判断左半 [left, mid] 是否有序 8        if nums[left] <= nums[mid]: 9            # 左半有序10            if nums[left] <= target < nums[mid]:11                right = mid - 112            else:13                left = mid + 114        else:15            # 右半 [mid, right] 有序16            if nums[mid] < target <= nums[right]:17                left = mid + 118            else:19                right = mid - 120    return -1

若数组未旋转（k=0），算法是否仍然正确？

时间复杂度是？

若题目改为"允许重复值"（LeetCode 81），核心难点是？

为什么本题不直接"先二分找旋转点 k，再在两段内分别二分 target"？

关卡 2 · 寻找峰值

学习目标

理解"二分不一定要排序"——只要能保证"砍掉的那半一定不是答案"就能二分。配合 right = mid 写法时循环条件必须用 < 防死循环，是写二分的常见陷阱。

#162寻找峰值中等

♥♥♥♥♥+0 XP🔥 0

0 / 12

📝 题目

峰值元素是指其值严格大于左右相邻值的元素。给你一个整数数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回任何一个峰值所在位置即可。

你可以假设 nums[-1] = nums[n] = -∞，也就是说边界两侧默认是负无穷。

你必须实现时间复杂度为 O(log n) 的算法。

示例 1

输入nums = [1, 2, 3, 1]

输出2

💡 nums[2]=3 是峰值

示例 2

输入nums = [1, 2, 1, 3, 5, 6, 4]

输出5

💡 索引 1 和 5 都是峰值，返回任一个

示例 3

输入nums = [1]

输出0

💡 单元素也算峰值（左右是 -∞）

约束

• 1 ≤ nums.length ≤ 1000
• -2³¹ ≤ nums[i] ≤ 2³¹ - 1
• 对所有有效的 i，nums[i] != nums[i + 1]

💡 思路：比较 nums[mid] 与 nums[mid+1]：上升段的右侧一定存在峰（沿上升一直走必撞顶），下降段的左侧一定存在峰。每次砍掉一半，O(log n)。题目"相邻不等 + 边界 -∞"两个条件保证整段不可能完全单调，必有峰存在。

✅ 完整解法

时间 O(log n) · 空间 O(1)

先把整段解法看懂，下面的选择题是对这段代码逐行的理解检验。

 1def findPeakElement(nums: list[int]) -> int: 2    left, right = 0, len(nums) - 1 3    while left < right: 4        mid = (left + right) // 2 5        if nums[mid] > nums[mid + 1]: 6            # 下降段，峰在 [left, mid] 7            right = mid 8        else: 9            # 上升段，峰在 [mid + 1, right]10            left = mid + 111    return left

🐞 单步可视化

示例：nums = [1, 2, 1, 3, 5, 6, 4]

代码L2

 1def findPeakElement(nums: list[int]) -> int: 2    left, right = 0, len(nums) - 1 3    while left < right: 4        mid = (left + right) // 2 5        if nums[mid] > nums[mid + 1]: 6            # 下降段，峰在 [left, mid] 7            right = mid 8        else: 9            # 上升段，峰在 [mid + 1, right]10            left = mid + 111    return left

数据流

L0R6

nums

0

1

L

1

2

2

1

3

3

4

5

5

6

6

4

R

1 / 14初始化 left=0, right=6（边界两侧默认 -∞）

速度 慢中快

🧠 理解检验

每题都对应解法的某一行或某个决策

本题为什么能用二分而不是必须 O(n) 扫描？

比较 nums[mid] 与 nums[mid+1] 时，nums[mid] > nums[mid+1] 意味着？

 1def findPeakElement(nums: list[int]) -> int: 2    left, right = 0, len(nums) - 1 3    while left < right: 4        mid = (left + right) // 2 5        if nums[mid] > nums[mid + 1]: 6            # 下降段，峰在 [left, mid] 7            right = mid 8        else: 9            # 上升段，峰在 [mid + 1, right]10            left = mid + 111    return left

nums[mid] < nums[mid+1] 时应该把 left 设为？

 1def findPeakElement(nums: list[int]) -> int: 2    left, right = 0, len(nums) - 1 3    while left < right: 4        mid = (left + right) // 2 5        if nums[mid] > nums[mid + 1]: 6            # 下降段，峰在 [left, mid] 7            right = mid 8        else: 9            # 上升段，峰在 [mid + 1, right]10            left = mid + 111    return left

当 nums[mid] > nums[mid+1] 时为什么用 right = mid 而非 right = mid - 1？

 1def findPeakElement(nums: list[int]) -> int: 2    left, right = 0, len(nums) - 1 3    while left < right: 4        mid = (left + right) // 2 5        if nums[mid] > nums[mid + 1]: 6            # 下降段，峰在 [left, mid] 7            right = mid 8        else: 9            # 上升段，峰在 [mid + 1, right]10            left = mid + 111    return left

循环条件应该用 < 还是 <=？

 1def findPeakElement(nums: list[int]) -> int: 2    left, right = 0, len(nums) - 1 3    while left < right: 4        mid = (left + right) // 2 5        if nums[mid] > nums[mid + 1]: 6            # 下降段，峰在 [left, mid] 7            right = mid 8        else: 9            # 上升段，峰在 [mid + 1, right]10            left = mid + 111    return left

循环退出时应该返回什么？

 1def findPeakElement(nums: list[int]) -> int: 2    left, right = 0, len(nums) - 1 3    while left < right: 4        mid = (left + right) // 2 5        if nums[mid] > nums[mid + 1]: 6            # 下降段，峰在 [left, mid] 7            right = mid 8        else: 9            # 上升段，峰在 [mid + 1, right]10            left = mid + 111    return left

访问 nums[mid + 1] 是否会越界？

若数组整体单调递增（如 [1,2,3,4,5]），算法返回什么？

题目"返回任意峰"的设计对算法选择的影响？

时间复杂度是？

空间复杂度是？

把"nums[mid] > nums[mid+1]"换成"nums[mid] > nums[mid-1]"是否同样可行？

关卡 3 · 寻找两个正序数组的中位数

学习目标

学会把"求中位数"重新建模成"切两刀 + 满足两不等式"的二分问题。这是 hard 二分题的通用思路：当朴素方法是 O(m+n) 时，先想"能不能转成切点二分"。

#4寻找两个正序数组的中位数困难

♥♥♥♥♥+0 XP🔥 0

0 / 13

📝 题目

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的中位数。

算法的时间复杂度应该为 O(log (m + n))。

示例 1

输入nums1 = [1, 3], nums2 = [2]

输出2.00000

💡 合并后 [1,2,3]，中位数 2

示例 2

输入nums1 = [1, 2], nums2 = [3, 4]

输出2.50000

💡 合并后 [1,2,3,4]，中位数 (2+3)/2

示例 3

输入nums1 = [], nums2 = [1]

输出1.00000

约束

• nums1.length == m, nums2.length == n
• 0 ≤ m, n ≤ 1000
• 1 ≤ m + n ≤ 2000
• -10⁶ ≤ nums1[i], nums2[i] ≤ 10⁶

💡 思路：把"找中位数"转化为"在两个数组里各切一刀，使左半总长 = (m+n+1)//2、且左半最大 ≤ 右半最小"。一旦在较短数组上确定切点 i，另一数组切点 j = total_left - i 由长度约束唯一决定。对 i 做二分：l1 > r2 说明 nums1 切多了要左移，l2 > r1 说明切少了要右移。在较短数组上二分把复杂度压到 O(log min(m, n))。

✅ 完整解法

时间 O(log min(m, n)) · 空间 O(1)

先把整段解法看懂，下面的选择题是对这段代码逐行的理解检验。

 1def findMedianSortedArrays(nums1: list[int], nums2: list[int]) -> float: 2    # 始终对较短的数组做二分，保证复杂度是 O(log min(m, n)) 3    if len(nums1) > len(nums2): 4        nums1, nums2 = nums2, nums1 5    m, n = len(nums1), len(nums2) 6    total_left = (m + n + 1) // 2   # 左半总长（奇数时多 1 在左） 7  8    lo, hi = 0, m                   # 在 nums1 上切的位置 i ∈ [0, m] 9    INF = float(「inf」)10    while lo <= hi:11        i = (lo + hi) // 212        j = total_left - i13 14        l1 = -INF if i == 0 else nums1[i - 1]15        r1 = INF if i == m else nums1[i]16        l2 = -INF if j == 0 else nums2[j - 1]17        r2 = INF if j == n else nums2[j]18 19        if l1 <= r2 and l2 <= r1:20            # 切点合法：左半最大 ≤ 右半最小21            if (m + n) % 2 == 1:22                return float(max(l1, l2))23            return (max(l1, l2) + min(r1, r2)) / 224        elif l1 > r2:25            hi = i - 1              # 在 nums1 中切得太靠右26        else:27            lo = i + 1              # 在 nums1 中切得太靠左28    return 0.0                       # 题目保证有解，永远到不了

🐞 单步可视化

示例：nums1 = [1, 2], nums2 = [3, 4]

代码L1

 1def findMedianSortedArrays(nums1: list[int], nums2: list[int]) -> float: 2    # 始终对较短的数组做二分，保证复杂度是 O(log min(m, n)) 3    if len(nums1) > len(nums2): 4        nums1, nums2 = nums2, nums1 5    m, n = len(nums1), len(nums2) 6    total_left = (m + n + 1) // 2   # 左半总长（奇数时多 1 在左） 7  8    lo, hi = 0, m                   # 在 nums1 上切的位置 i ∈ [0, m] 9    INF = float(「inf」)10    while lo <= hi:11        i = (lo + hi) // 212        j = total_left - i13 14        l1 = -INF if i == 0 else nums1[i - 1]15        r1 = INF if i == m else nums1[i]16        l2 = -INF if j == 0 else nums2[j - 1]17        r2 = INF if j == n else nums2[j]18 19        if l1 <= r2 and l2 <= r1:20            # 切点合法：左半最大 ≤ 右半最小21            if (m + n) % 2 == 1:22                return float(max(l1, l2))23            return (max(l1, l2) + min(r1, r2)) / 224        elif l1 > r2:25            hi = i - 1              # 在 nums1 中切得太靠右26        else:27            lo = i + 1              # 在 nums1 中切得太靠左28    return 0.0                       # 题目保证有解，永远到不了

数据流

nums1[1,2]nums2[3,4]

nums1（较短，二分切点 i 在它上面）

0

1

1

2

nums2

0

3

1

4

1 / 30输入 nums1=[1,2], nums2=[3,4]

速度 慢中快

🧠 理解检验

每题都对应解法的某一行或某个决策

本题为什么不能直接合并两数组找中位数？

"切两刀使左半总长为 (m+n+1)//2"的设计，对奇偶情形如何统一？

为什么要先 swap 让 nums1 是较短的？

 1def findMedianSortedArrays(nums1: list[int], nums2: list[int]) -> float: 2    # 始终对较短的数组做二分，保证复杂度是 O(log min(m, n)) 3    if len(nums1) > len(nums2): 4        nums1, nums2 = nums2, nums1 5    m, n = len(nums1), len(nums2) 6    total_left = (m + n + 1) // 2   # 左半总长（奇数时多 1 在左） 7  8    lo, hi = 0, m                   # 在 nums1 上切的位置 i ∈ [0, m] 9    INF = float(「inf」)10    while lo <= hi:11        i = (lo + hi) // 212        j = total_left - i13 14        l1 = -INF if i == 0 else nums1[i - 1]15        r1 = INF if i == m else nums1[i]16        l2 = -INF if j == 0 else nums2[j - 1]17        r2 = INF if j == n else nums2[j]18 19        if l1 <= r2 and l2 <= r1:20            # 切点合法：左半最大 ≤ 右半最小21            if (m + n) % 2 == 1:22                return float(max(l1, l2))23            return (max(l1, l2) + min(r1, r2)) / 224        elif l1 > r2:25            hi = i - 1              # 在 nums1 中切得太靠右26        else:27            lo = i + 1              # 在 nums1 中切得太靠左28    return 0.0                       # 题目保证有解，永远到不了

l1 = -inf if i == 0 else nums1[i-1] 这行哨兵的作用是？

 1def findMedianSortedArrays(nums1: list[int], nums2: list[int]) -> float: 2    # 始终对较短的数组做二分，保证复杂度是 O(log min(m, n)) 3    if len(nums1) > len(nums2): 4        nums1, nums2 = nums2, nums1 5    m, n = len(nums1), len(nums2) 6    total_left = (m + n + 1) // 2   # 左半总长（奇数时多 1 在左） 7  8    lo, hi = 0, m                   # 在 nums1 上切的位置 i ∈ [0, m] 9    INF = float(「inf」)10    while lo <= hi:11        i = (lo + hi) // 212        j = total_left - i13 14        l1 = -INF if i == 0 else nums1[i - 1]15        r1 = INF if i == m else nums1[i]16        l2 = -INF if j == 0 else nums2[j - 1]17        r2 = INF if j == n else nums2[j]18 19        if l1 <= r2 and l2 <= r1:20            # 切点合法：左半最大 ≤ 右半最小21            if (m + n) % 2 == 1:22                return float(max(l1, l2))23            return (max(l1, l2) + min(r1, r2)) / 224        elif l1 > r2:25            hi = i - 1              # 在 nums1 中切得太靠右26        else:27            lo = i + 1              # 在 nums1 中切得太靠左28    return 0.0                       # 题目保证有解，永远到不了

切点合法的判定条件应该是？

 1def findMedianSortedArrays(nums1: list[int], nums2: list[int]) -> float: 2    # 始终对较短的数组做二分，保证复杂度是 O(log min(m, n)) 3    if len(nums1) > len(nums2): 4        nums1, nums2 = nums2, nums1 5    m, n = len(nums1), len(nums2) 6    total_left = (m + n + 1) // 2   # 左半总长（奇数时多 1 在左） 7  8    lo, hi = 0, m                   # 在 nums1 上切的位置 i ∈ [0, m] 9    INF = float(「inf」)10    while lo <= hi:11        i = (lo + hi) // 212        j = total_left - i13 14        l1 = -INF if i == 0 else nums1[i - 1]15        r1 = INF if i == m else nums1[i]16        l2 = -INF if j == 0 else nums2[j - 1]17        r2 = INF if j == n else nums2[j]18 19        if l1 <= r2 and l2 <= r1:20            # 切点合法：左半最大 ≤ 右半最小21            if (m + n) % 2 == 1:22                return float(max(l1, l2))23            return (max(l1, l2) + min(r1, r2)) / 224        elif l1 > r2:25            hi = i - 1              # 在 nums1 中切得太靠右26        else:27            lo = i + 1              # 在 nums1 中切得太靠左28    return 0.0                       # 题目保证有解，永远到不了

当 l1 > r2 时该怎么调整？

 1def findMedianSortedArrays(nums1: list[int], nums2: list[int]) -> float: 2    # 始终对较短的数组做二分，保证复杂度是 O(log min(m, n)) 3    if len(nums1) > len(nums2): 4        nums1, nums2 = nums2, nums1 5    m, n = len(nums1), len(nums2) 6    total_left = (m + n + 1) // 2   # 左半总长（奇数时多 1 在左） 7  8    lo, hi = 0, m                   # 在 nums1 上切的位置 i ∈ [0, m] 9    INF = float(「inf」)10    while lo <= hi:11        i = (lo + hi) // 212        j = total_left - i13 14        l1 = -INF if i == 0 else nums1[i - 1]15        r1 = INF if i == m else nums1[i]16        l2 = -INF if j == 0 else nums2[j - 1]17        r2 = INF if j == n else nums2[j]18 19        if l1 <= r2 and l2 <= r1:20            # 切点合法：左半最大 ≤ 右半最小21            if (m + n) % 2 == 1:22                return float(max(l1, l2))23            return (max(l1, l2) + min(r1, r2)) / 224        elif l1 > r2:25            hi = i - 1              # 在 nums1 中切得太靠右26        else:27            lo = i + 1              # 在 nums1 中切得太靠左28    return 0.0                       # 题目保证有解，永远到不了

当 l2 > r1 时该怎么调整？

 1def findMedianSortedArrays(nums1: list[int], nums2: list[int]) -> float: 2    # 始终对较短的数组做二分，保证复杂度是 O(log min(m, n)) 3    if len(nums1) > len(nums2): 4        nums1, nums2 = nums2, nums1 5    m, n = len(nums1), len(nums2) 6    total_left = (m + n + 1) // 2   # 左半总长（奇数时多 1 在左） 7  8    lo, hi = 0, m                   # 在 nums1 上切的位置 i ∈ [0, m] 9    INF = float(「inf」)10    while lo <= hi:11        i = (lo + hi) // 212        j = total_left - i13 14        l1 = -INF if i == 0 else nums1[i - 1]15        r1 = INF if i == m else nums1[i]16        l2 = -INF if j == 0 else nums2[j - 1]17        r2 = INF if j == n else nums2[j]18 19        if l1 <= r2 and l2 <= r1:20            # 切点合法：左半最大 ≤ 右半最小21            if (m + n) % 2 == 1:22                return float(max(l1, l2))23            return (max(l1, l2) + min(r1, r2)) / 224        elif l1 > r2:25            hi = i - 1              # 在 nums1 中切得太靠右26        else:27            lo = i + 1              # 在 nums1 中切得太靠左28    return 0.0                       # 题目保证有解，永远到不了

二分 i 的上界 hi 应该初始化为 m 还是 m - 1？

 1def findMedianSortedArrays(nums1: list[int], nums2: list[int]) -> float: 2    # 始终对较短的数组做二分，保证复杂度是 O(log min(m, n)) 3    if len(nums1) > len(nums2): 4        nums1, nums2 = nums2, nums1 5    m, n = len(nums1), len(nums2) 6    total_left = (m + n + 1) // 2   # 左半总长（奇数时多 1 在左） 7  8    lo, hi = 0, m                   # 在 nums1 上切的位置 i ∈ [0, m] 9    INF = float(「inf」)10    while lo <= hi:11        i = (lo + hi) // 212        j = total_left - i13 14        l1 = -INF if i == 0 else nums1[i - 1]15        r1 = INF if i == m else nums1[i]16        l2 = -INF if j == 0 else nums2[j - 1]17        r2 = INF if j == n else nums2[j]18 19        if l1 <= r2 and l2 <= r1:20            # 切点合法：左半最大 ≤ 右半最小21            if (m + n) % 2 == 1:22                return float(max(l1, l2))23            return (max(l1, l2) + min(r1, r2)) / 224        elif l1 > r2:25            hi = i - 1              # 在 nums1 中切得太靠右26        else:27            lo = i + 1              # 在 nums1 中切得太靠左28    return 0.0                       # 题目保证有解，永远到不了

奇数情形 (m+n) 为奇时，中位数应取？

 1def findMedianSortedArrays(nums1: list[int], nums2: list[int]) -> float: 2    # 始终对较短的数组做二分，保证复杂度是 O(log min(m, n)) 3    if len(nums1) > len(nums2): 4        nums1, nums2 = nums2, nums1 5    m, n = len(nums1), len(nums2) 6    total_left = (m + n + 1) // 2   # 左半总长（奇数时多 1 在左） 7  8    lo, hi = 0, m                   # 在 nums1 上切的位置 i ∈ [0, m] 9    INF = float(「inf」)10    while lo <= hi:11        i = (lo + hi) // 212        j = total_left - i13 14        l1 = -INF if i == 0 else nums1[i - 1]15        r1 = INF if i == m else nums1[i]16        l2 = -INF if j == 0 else nums2[j - 1]17        r2 = INF if j == n else nums2[j]18 19        if l1 <= r2 and l2 <= r1:20            # 切点合法：左半最大 ≤ 右半最小21            if (m + n) % 2 == 1:22                return float(max(l1, l2))23            return (max(l1, l2) + min(r1, r2)) / 224        elif l1 > r2:25            hi = i - 1              # 在 nums1 中切得太靠右26        else:27            lo = i + 1              # 在 nums1 中切得太靠左28    return 0.0                       # 题目保证有解，永远到不了

若 nums1 为空（m == 0），算法应该返回什么？

时间复杂度是？

空间复杂度是？

Python 里 nums1, nums2 = nums2, nums1 这种写法的本质是？

同 pattern 索引（hot100 同类题）

题号	题名	难度	关键变形
35	搜索插入位置	简单	标准二分模板，找第一个 ≥ target 的下标
34	在排序数组中查找元素的第一个和最后一个位置	中等	两次二分：lower_bound 和 upper_bound
153	寻找旋转排序数组中的最小值	中等	与 33 同骨架，只是不找 target 而是找拐点
74	搜索二维矩阵	中等	把 m×n 矩阵看成长度 m·n 的有序数组，下标 ↔ (行,列) 互转
240	搜索二维矩阵 II	中等	从右上角出发的"阶梯二分"，每步排除一行或一列

面试常踩

1. right = mid 必配 while left < right——任何写 right = mid（不严格收缩）的版本，循环条件都不能是 <=，否则当 left==right==mid 时陷入死循环。
2. 闭区间 vs 左闭右开要选一种用到底——混用最容易写出"差一格"的 bug。建议入门期固定用闭区间 [left, right] + while left <= right + right=mid-1 / left=mid+1。
3. mid 计算用 left + (right - left) // 2——Python 不溢出但跨语言通用；写这个版本是面试加分项。
4. 链式比较 a < b < c——Python 特性等价于 a < b and b < c，且 b 只求值一次。33 题里 nums[left] <= target < nums[mid] 写得地道。