Core Insight Each comparison proves that half of the remaining search space cannot contain the answer.
Common Pitfall Choose inclusive or exclusive bounds once and update them consistently.
Description
Find the median of two sorted arrays with O(log(m+n)) complexity.
Constraints
- Time Complexity:
O(log(m+n)) - Space Complexity:
O(1)
Tags
arraybinary-searchdivide-and-conquer
Implementation Plan Translate the invariant into these small, testable moves.
- Set the initial bounds.
- Compute a midpoint.
- Use the monotonic condition to discard one half.
- Return when found or when the bounds cross.
def findMedianSortedArrays(nums1, nums2):
A, B = nums1, nums2
total = len(nums1) + len(nums2)
half = total // 2
if len(B) < len(A):
A, B = B, A
l, r = 0, len(A) - 1
while True:
i = (l + r) // 2
j = half - i - 2
Aleft = A[i] if i >= 0 else float("-infinity")
Aright = A[i + 1] if (i + 1) < len(A) else float("infinity")
Bleft = B[j] if j >= 0 else float("-infinity")
Bright = B[j + 1] if (j + 1) < len(B) else float("infinity")
if Aleft <= Bright and Bleft <= Aright:
if total % 2:
return min(Aright, Bright)
return (max(Aleft, Bleft) + min(Aright, Bright)) / 2
elif Aleft > Bright:
r = i - 1
else:
l = i + 1