Today is a Saturday Deep Dive day. The full deep dive content has been written to the deepdive archive file.
Individual section summaries are not generated on Saturdays — see the deepdive file for comprehensive content covering the selected topic in full bilingual detail.
Deep dive topic: Median of Two Sorted Arrays (LeetCode #4)
Date: 2026-05-09
Today is a Saturday Deep Dive day. The full deep dive content has been written to the deepdive archive file.
Individual section summaries are not generated on Saturdays — see the deepdive file for comprehensive content covering the selected topic in full bilingual detail.
Deep dive topic: Median of Two Sorted Arrays (LeetCode #4)
Date: 2026-05-09
Today is a Saturday Deep Dive day. The full deep dive content has been written to the deepdive archive file.
Individual section summaries are not generated on Saturdays — see the deepdive file for comprehensive content covering the selected topic in full bilingual detail.
Deep dive topic: Median of Two Sorted Arrays (LeetCode #4)
Date: 2026-05-09
Today is a Saturday Deep Dive day. The full deep dive content has been written to the deepdive archive file.
Individual section summaries are not generated on Saturdays — see the deepdive file for comprehensive content covering the selected topic in full bilingual detail.
Deep dive topic: Median of Two Sorted Arrays (LeetCode #4)
Date: 2026-05-09
Today is a Saturday Deep Dive day. The full deep dive content has been written to the deepdive archive file.
Individual section summaries are not generated on Saturdays — see the deepdive file for comprehensive content covering the selected topic in full bilingual detail.
Deep dive topic: Median of Two Sorted Arrays (LeetCode #4)
Date: 2026-05-09
🔬 Saturday Deep Dive: Median of Two Sorted Arrays — The Hardest Easy Concept (15 min read)
📊 NeetCode: 33/150 · SysDesign: 32/40 · Behavioral: 32/40 · Frontend: 32/50 · AI: 16/30
🔥 38-day streak!
这道题是 LeetCode #4，难度标注为 Hard，也是整个 NeetCode 150 中公认最难的二分搜索题之一。它不仅仅是"找中位数"这么简单——它要求你在 O(log(m+n)) 时间复杂度内完成，这意味着你不能合并两个数组再找中位数。正确解法需要对二分搜索有深刻理解：不是搜索具体值，而是搜索分割位置。
This is LeetCode #4 — one of the most notoriously tricky Hard problems in the entire NeetCode 150. The naive approach (merge + find middle) is O(m+n) and trivial. The interviewer wants O(log(min(m,n))). That constraint forces you to think about binary search not as "find a value" but as "find the correct partition" — a fundamental mental model shift that unlocks a whole class of problems.
Why it matters: This problem shows up in FAANG interviews precisely because it tests whether you truly understand binary search at a deep level, not just pattern-matching. The technique generalizes to finding k-th elements, weighted medians, and even some geometry problems.
中位数将一个有序序列分成两半：左半部分的所有元素都 ≤ 右半部分的所有元素。
The median divides a sorted sequence into two equal halves where every element on the left ≤ every element on the right.
给定两个排序数组 nums1 和 nums2，我们要找到一个分割点，使得：
Given two sorted arrays nums1 and nums2, we need to find partitions such that:
nums1: [... L1 | R1 ...]
nums2: [... L2 | R2 ...]满足以下两个条件：
Meeting both conditions:
Left side has same count as right side (or differs by 1)
L1 ≤ R2 AND L2 ≤ R1 (all left elements ≤ all right elements)
一旦找到这样的分割：
Once found:
median = (max(L1, L2) + min(R1, R2)) / 2median = max(L1, L2)（若左边多一个）关键：我们只需在较短的数组上二分。一旦确定了 nums1 的分割位置 i，nums2 的分割位置 j 就被自动确定了：
Key insight: we only binary search on the shorter array. Once we fix partition i in nums1, partition j in nums2 is fully determined by the total-half-length constraint:
i + j = half_len = (m + n + 1) // 2
j = half_len - i所以整个问题变成：在 nums1 的下标范围 [0, m] 上二分，找到满足条件的 i。
So the problem reduces to: binary search over [0, m] in nums1 to find valid i.
def findMedianSortedArrays_naive(nums1: list[int], nums2: list[int]) -> float:
# Merge and sort — O(m+n) time, O(m+n) space
# NOT acceptable if interviewer asks for O(log(m+n))
merged = sorted(nums1 + nums2)
n = len(merged)
if n % 2 == 1:
return float(merged[n // 2])
else:
return (merged[n // 2 - 1] + merged[n // 2]) / 2.0面试策略：先说"我可以用 O(m+n) 暴力合并，但你要求 O(log) 所以我来优化"。这展示了你的思维过程。
Interview strategy: Always state the naive solution first, then say "but we can do better with binary search."
def findMedianSortedArrays(nums1: list[int], nums2: list[int]) -> float:
# Always binary search on the SHORTER array for efficiency
# If nums1 is longer, swap them
A, B = nums1, nums2
if len(A) > len(B):
A, B = B, A
m, n = len(A), len(B)
# half_len: number of elements in the "left half" of the merged array
# The +1 handles odd total length — left half gets the extra element
half_len = (m + n + 1) // 2
# Binary search on partition point i in array A
# i = number of elements taken from A for the left half
# j = number of elements taken from B for the left half (derived)
lo, hi = 0, m
while lo <= hi:
i = (lo + hi) // 2 # partition in A: A[:i] | A[i:]
j = half_len - i # partition in B: B[:j] | B[j:]
# Boundary values — use -inf/+inf to handle edge cases
# (when partition is at the start or end of an array)
A_left = A[i - 1] if i > 0 else float('-inf') # last elem of A's left half
A_right = A[i] if i < m else float('inf') # first elem of A's right half
B_left = B[j - 1] if j > 0 else float('-inf') # last elem of B's left half
B_right = B[j] if j < n else float('inf') # first elem of B's right half
# Check if we found the correct partition:
# All left elements must be ≤ all right elements
if A_left <= B_right and B_left <= A_right:
# FOUND! Compute median
if (m + n) % 2 == 1:
# Odd total: median is the max of both left halves
return float(max(A_left, B_left))
else:
# Even total: average of max-left and min-right
return (max(A_left, B_left) + min(A_right, B_right)) / 2.0
elif A_left > B_right:
# A's left is too big — move partition left in A
hi = i - 1
else:
# B_left > A_right: A's left is too small — move partition right in A
lo = i + 1
# Should never reach here if inputs are valid sorted arrays
raise ValueError("Input arrays are not sorted or otherwise invalid")| 方法 / Approach | 时间 / Time | 空间 / Space |
|---|---|---|
| Naive merge | O(m+n) | O(m+n) |
| Binary search | O(log(min(m,n))) | O(1) |
1. 分割在数组边界 / Partition at array boundary
# When i=0, there's nothing on A's left — use -inf as sentinel
# When i=m, there's nothing on A's right — use +inf as sentinel
A_left = A[i - 1] if i > 0 else float('-inf')
A_right = A[i] if i < m else float('inf')如果不处理边界，你会得到 IndexError。这是最常见的 bug 来源。
If you don't handle boundaries, you get IndexError. This is the #1 bug source.
2. 奇偶性处理 / Odd vs Even Length
half_len = (m + n + 1) // 2 # The +1 is critical!
# Without +1, for odd total length, left half gets fewer elements
# For even: left=right=n/2 elements, median=(max_left+min_right)/2
# For odd: left gets one extra, median=max_left3. 必须在较短数组上二分 / Must binary search the shorter array
if len(A) > len(B):
A, B = B, A
# This ensures j = half_len - i is always valid (0 <= j <= n)
# If A is longer, j could go negative!4. 两个数组都为空 / Edge: empty inputs
# LC guarantees at least one is non-empty, but in real code:
if not A and not B: raise ValueError("both empty")
# The -inf/+inf sentinels handle when one array is empty1. 数据库 percentile 查询 / Database percentile queries
当你在 PostgreSQL 中运行 PERCENTILE_CONT(0.5) 时，数据库内部需要高效计算中位数。对于已经分区的数据，其核心思想与这道题类似——找到两个有序集合的分割点。
PERCENTILE_CONT(0.5) in PostgreSQL for partitioned/sharded data uses similar "find the partition" logic across sorted segments.
2. 分布式系统中的 p50/p99 延迟 / p50/p99 latency in distributed systems
监控系统（Datadog, Prometheus）在聚合多台机器的延迟数据时，每台机器维护自己的有序延迟数组。合并后找 p50 就是这道题的变体。
Monitoring systems aggregate latency histograms from multiple nodes. Finding p50 across sorted arrays from 10 pods is this exact problem.
3. 流媒体中位数 / Streaming median (variant)
LeetCode #295 "Find Median from Data Stream" 用两个堆（max-heap + min-heap）维护中位数——这是对"维护两个有序结构的分割点"这一思想的直接应用。
LC #295 uses two heaps to maintain the partition point dynamically — the same conceptual core.
4. 二分搜索思想的泛化 / Generalizing the "partition binary search" idea
The pattern: binary search on a partition/decision variable, not a concrete value — generalizes to split-array problems, capacity optimization, etc.
以下是面试官可能追问的 5 个问题和简洁答案：
Q1: 为什么要在较短的数组上二分？/ Why binary search on the shorter array?
因为较短数组长度为 m，二分复杂度是 O(log m)。同时，j = half_len - i 需要满足 0 ≤ j ≤ n，在较短数组上二分可以保证 j 始终有效。如果 m > n，交换两个数组即可。
To get O(log(min(m,n))) and to guarantee j = half_len - i stays in [0, n]. If we search the longer array, j could go out of bounds.
Q2: 如果数组没有排序怎么办？/ What if arrays aren't sorted?
题目保证有序。实际中需要先排序（O(m log m + n log n)），此时不如直接合并找中位数。如果数据流式到来（无法预排序），用两个堆的方案（LC #295）更合适。
The problem guarantees sorted. If not, sort first — but then O((m+n)log(m+n)) merge is simpler. For streaming unsorted data, use the two-heap approach (LC #295).
Q3: 这道题能用递归解吗？/ Can this be solved recursively?
可以。经典递归解法是"找两个有序数组中第 k 小的数"，每次递归排除 k/2 个元素，时间复杂度同样是 O(log(m+n))。但迭代二分更直观，代码更简洁，面试推荐迭代版本。
Yes — recursive "find k-th element" approach works: each call eliminates k/2 elements from consideration. Same O(log(m+n)) complexity, but the iterative partition approach is cleaner to code under pressure.
Q4: 如果有多个重复元素？/ What about duplicates?
完全没问题。算法不依赖元素唯一性——它只比较 A_left ≤ B_right 和 B_left ≤ A_right，重复元素不影响大小关系的判断。用测试用例 [1,1] 和 [1,1] 验证：答案 1.0，算法返回 max(1,1) = 1.0 ✓。
No problem. The comparisons A_left ≤ B_right handle duplicates correctly. Test: [1,1] and [1,1] → median 1.0. Algorithm: max(1,1) = 1.0 ✓.
Q5: 如何扩展到 k 个有序数组？/ How would you extend this to k sorted arrays?
对 k 个数组做二分搜索不再直接适用（搜索空间是 k 维的）。常见方法：
(a) 最小堆合并（O(N log k)，N 是总元素数）
(b) 分治：两两合并为一个，递归处理（O(N log k)）
(c) 若只要中位数，可以用采样估计（近似算法）
Binary search across k arrays isn't straightforward (k-dimensional search space). Better approaches: (a) min-heap k-way merge O(N log k), (b) divide-and-conquer pairwise merge, (c) sampling-based approximation for very large k.
Test input: nums1 = [1, 3], nums2 = [2, 4]
Partition diagram:
Code trace:
A=[1,3], B=[2,4], m=2, n=2, half_len=2
lo=0, hi=2
→ i=1, j=1
→ A_left=A[0]=1, A_right=A[1]=3
→ B_left=B[0]=2, B_right=B[1]=4
→ 1 ≤ 4 ✓ AND 2 ≤ 3 ✓ → FOUND
→ even total: (max(1,2) + min(3,4))/2 = (2+3)/2 = 2.5✅ Diagram matches code exactly. The partition line in the diagram corresponds directly to i=1, j=1 in the code, and the left/right boundary values are the same in both.