Median of Two Sorted Arrays
You'll learn how to find the median of two sorted arrays in O(log n) time using binary search on partition points.
The Core Challenge
Imagine you have two sorted arrays and need to find the median as if they were merged together—but without actually merging them (which would take O(n) time). The trick is to use binary search to find the right partition points in both arrays that divide all elements into a "left half" and "right half" with the median at the boundary.
How It Works
Think of laying two sorted arrays side by side. You need to draw a vertical line through each array such that:
- All elements to the left of both lines are ≤ all elements to the right
- The left side contains exactly half the total elements (or one more if odd length)
You binary search on partition positions in the shorter array (for efficiency). For each partition guess in array A, you calculate the corresponding partition in array B mathematically. Then check if your partitions are valid by comparing the boundary elements:
maxLeftA ≤ minRightBmaxLeftB ≤ minRightA
If the left side has too-large elements, adjust your search left. If the right side has too-small elements, search right. When valid, the median is the average of the max of left sides and min of right sides (or just one value for odd total length).
Why O(log n)?
You're binary searching on partition positions (0 to length of shorter array), so you make O(log(min(m,n))) comparisons instead of scanning all elements.
Key Takeaway: By binary searching partition points in two sorted arrays and validating boundary conditions, you can find the median in logarithmic time—a powerful application of divide-and-conquer thinking to avoid linear merging.