This problem follows the Binary Search Partition pattern, commonly found in the Binary Search category. Recognizing this pattern is key to solving it efficiently in an interview setting.
Binary search on the smaller array to find the correct partition point.
Binary search on the smaller array keeps it O(log(min(m,n))) — the partition in the larger array is determined by the smaller one.
A, B = shorter array, longer array
left, right = 0, len(A)
while left <= right:
i = (left + right) // 2
j = (len(A) + len(B) + 1) // 2 - i
if A[i-1] > B[j]: right = i - 1
elif B[j-1] > A[i]: left = i + 1
else: # valid partition
maxLeft = max(A[i-1], B[j-1])
if (len(A)+len(B)) % 2: return maxLeft
minRight = min(A[i], B[j])
return (maxLeft + minRight) / 2Practice Median of Two Sorted Arrays and similar Binary Search problems with flashcards. Build pattern recognition through active recall.
Practice this problem