Idea:
We want to partition both arrays into a left half and a right half such that:
len(left) = len(right) (or differs by at most 1 if total length is odd).
All elements in left ≤ all elements in right.
If we can find such a partition, then the median is either:
max(left) if total length is odd,
average(max(left), min(right)) if total length is even.
How to find the partition?
Binary search on how many elements we take from the smaller array (nums1).
Suppose we take i elements from nums1, then we must take j = (m+n)//2 - i elements from nums2.
We check the partition condition:
nums1[i-1] <= nums2[j] (if i > 0 and j < n)
nums2[j-1] <= nums1[i] (if j > 0 and i < m)
If the partition is invalid, adjust i up or down.
When it’s valid, compute the median.
class Solution: def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float: # Ensure nums1 is the smaller array if len(nums1) > len(nums2): nums1, nums2 = nums2, nums1 m, n = len(nums1), len(nums2) total = m + n half = total // 2 left, right = 0, m while True: i = (left + right) // 2 # partition in nums1 j = half - i # partition in nums2 left1 = nums1[i-1] if i > 0 else float("-inf") right1 = nums1[i] if i < m else float("inf") left2 = nums2[j-1] if j > 0 else float("-inf") right2 = nums2[j] if j < n else float("inf") if left1 <= right2 and left2 <= right1: # correct partition if total % 2: # odd return min(right1, right2) return (max(left1, left2) + min(right1, right2)) / 2 elif left1 > right2: # move left in nums1 right = i - 1 else: # move right in nums1 left = i + 1