LeetCode 4 Median of Two Sorted Arrays - Example and Complexity Analysis

Trace nums1 = [1, 3, 8], nums2 = [7, 9, 10, 11]. Total = 7. Left half needs 4 elements.

Binary search on nums1 (smaller). Range: [0, 3].

i = 1 (take 1 from nums1), j = 3 (take 3 from nums2). Left: [1, 7, 9, 10]. Right: [3, 8, 11].

Check: nums1[0] = 1 <= nums2[3] = 11 ✓. nums2[2] = 10 <= nums1[1] = 3? No, 10 > 3. Move right in nums1.

i = 2, j = 2. Left: [1, 3, 7, 9]. Right: [8, 10, 11].

Check: nums1[1] = 3 <= nums2[2] = 10 ✓. nums2[1] = 9 <= nums1[2] = 8? No, 9 > 8. Move right.

i = 3, j = 1. Left: [1, 3, 8, 7]. Right: [9, 10, 11].

Check: nums1[2] = 8 <= nums2[1] = 9 ✓. nums2[0] = 7 <= nums1[3]? Out of bounds, treat as ✓.

Median = max of left = max(8, 7) = 8.

Binary search on smaller array: $O(\log(\min(m, n)))$. $O(1)$ space.