Binary Search · LC #4
Median of Two Sorted Arrays
Find the median of two sorted arrays in O(log(min(m,n))) by binary searching for the correct partition point on the shorter array such that the left halves of both arrays together contain exactly the smaller half of all elements.
Statement
Problem & Approach
Problem statement, sample I/O, and key reasoning.
Given two sorted arrays `nums1` and `nums2` of size `m` and `n` respectively, return the median of the two sorted arrays. The overall run time complexity should be O(log(m+n)).
Sample I/O
Input: nums1 = [1,3], nums2 = [2] Output: 2.0 Input: nums1 = [1,2], nums2 = [3,4] Output: 2.5
Intuition
How to Think About It
Intuition
The median divides all combined elements into two equal halves. Binary search on the partition point `i` in the shorter array: for each `i`, the corresponding partition `j = half - i` in the longer array is determined. A valid partition satisfies `maxLeft_A <= minRight_B` and `maxLeft_B <= minRight_A` - adjust `i` left or right until valid.
Core Concept
Always binary search on the shorter array (length m) for O(log m) iterations. `half = (m+n+1)/2` ensures the left side has ⌈(m+n)/2⌉ elements. For partition `i` in A and `j=half-i` in B: if `A[i-1] > B[j]`, move `i` left (`r=i-1`); if `B[j-1] > A[i]`, move `i` right (`l=i+1`). Valid: return median from boundary elements using sentinel ±∞ for out-of-bounds.
When to use
Merging or querying statistics across two sorted datasets in O(log n); any problem that can be reduced to "find the k-th element in two sorted arrays".
When NOT to use
When O((m+n) log(m+n)) is acceptable (merge and sort); when the combined array is needed anyway.
Key Insights
What to Know Cold
- Always binary search on the shorter array - ensures O(log min(m,n)) and simplifies bound handling.
- Use ±∞ sentinels for out-of-bounds partition indices (i=0 or i=m) to unify the boundary cases without special-casing.
- The valid partition condition is symmetric: maxLeft_A ≤ minRight_B AND maxLeft_B ≤ minRight_A.
- For odd total, median = max(maxLeft_A, maxLeft_B); for even, average of max-left and min-right.
- The `half = (m+n+1)//2` formula (using integer division rounding up) correctly handles both odd and even totals with the same return logic.
3 examples
Worked Examples
Odd total - single median
nums1=[1,3], nums2=[2]. Combined=[1,2,3], median=2.
Binary search on shorter array (length 2). Find i=1 such that A[0]=1≤B[1]=∞ and B[0]=2≤A[1]=3. Valid. Odd total → return max(1,2)=2.
function findMedianSortedArrays(A: number[], B: number[]): number {
if (A.length > B.length) return findMedianSortedArrays(B, A);
const m=A.length, n=B.length, half=Math.floor((m+n+1)/2);
let l=0, r=m;
while(l<=r){
const i=l+Math.floor((r-l)/2), j=half-i;
const ml=i>0?A[i-1]:-Infinity, mr=i<m?A[i]:Infinity;
const nl=j>0?B[j-1]:-Infinity, nr=j<n?B[j]:Infinity;
if(ml<=nr&&nl<=mr){
if((m+n)%2===1) return Math.max(ml,nl);
return (Math.max(ml,nl)+Math.min(mr,nr))/2;
} else if(ml>nr) r=i-1; else l=i+1;
}
return 0;
}Output: 2.0
Validates odd-total path and sentinel handling.
Even total - average of two middle elements
nums1=[1,2], nums2=[3,4]. Combined=[1,2,3,4], median=(2+3)/2=2.5.
Partition: i=2 in A, j=0 in B. maxLeft_A=2, minRight_A=∞, maxLeft_B=-∞, minRight_B=3. Valid. Even → (max(2,-∞)+min(∞,3))/2 = (2+3)/2 = 2.5.
Output: 2.5
Even-total path; shows both inner elements are correctly identified.
One empty array
nums1=[], nums2=[1,2,3,4,5].
Binary search on shorter (empty). i always 0, j=half=3. Sentinels: maxLeft_A=-∞, minRight_A=∞. Valid at first iteration. Return median of B directly.
Output: 3.0
Edge case: one empty array; sentinels make it degenerate to single-array median.