Boundary update without `+1` / `-1`
Wrong move: Setting `lo = mid` or `hi = mid` can stall and create an infinite loop.
Usually fails on: Two-element ranges never converge.
Fix: Use `lo = mid + 1` or `hi = mid - 1` where appropriate.
A complete visual walkthrough of the binary search approach — from intuition to implementation.
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)).
Example 1:
Input: nums1 = [1,3], nums2 = [2] Output: 2.00000 Explanation: merged array = [1,2,3] and median is 2.
Example 2:
Input: nums1 = [1,2], nums2 = [3,4] Output: 2.50000 Explanation: merged array = [1,2,3,4] and median is (2 + 3) / 2 = 2.5.
Constraints:
nums1.length == mnums2.length == n0 <= m <= 10000 <= n <= 10001 <= m + n <= 2000-106 <= nums1[i], nums2[i] <= 106The naive approach merges both arrays and picks the middle element. Let's see it visually:
This works but runs in O(m + n) time. The problem demands O(log(m + n)), which means we need binary search — we can't afford to look at every element.
Key idea: We don't need to actually merge. We just need to find where the "cut" falls — the partition point that splits all elements into two equal halves.
Imagine drawing a vertical line through both arrays simultaneously, splitting the combined elements into a left half and a right half of equal size.
If we place i elements from nums1 on the left, then we must place j = half - i elements from nums2 on the left, where half = ⌈(m+n)/2⌉.
Left side has i + j = 4 elements. Right side has 3 elements. For 7 total elements, the median is the largest value on the left side.
A valid partition means every element on the left ≤ every element on the right. Since each array is already sorted internally, we only need to check the cross conditions:
In our example: left1=3 ≤ right2=7 ✓ and left2=5 ≤ right1=8 ✓ — both pass, so this partition is correct!
We only defined four boundary values: left1, right1, left2, right2. These four numbers are all we need to verify a partition and compute the median. We never touch the interior elements.
We binary search on i (the partition index in the smaller array). Since j is determined by i, moving i automatically adjusts j in the opposite direction.
Why the smaller array? We binary search on the smaller array (swap if needed) to guarantee j is never negative. If m ≤ n, then j = half − i ≥ 0 always holds. It also minimizes iterations: O(log(min(m,n))).
When i = 0 or i = m, one side of the partition in nums1 is empty. We use sentinel values to handle this cleanly:
int left1 = (i == 0) ? Integer.MIN_VALUE : nums1[i - 1]; int right1 = (i == m) ? Integer.MAX_VALUE : nums1[i]; int left2 = (j == 0) ? Integer.MIN_VALUE : nums2[j - 1]; int right2 = (j == n) ? Integer.MAX_VALUE : nums2[j];
var left1, right1, left2, right2 int if i == 0 { left1 = math.MinInt32 } else { left1 = nums1[i-1] } if i == m { right1 = math.MaxInt32 } else { right1 = nums1[i] } if j == 0 { left2 = math.MinInt32 } else { left2 = nums2[j-1] } if j == n { right2 = math.MaxInt32 } else { right2 = nums2[j] }
left1 = float("-inf") if i == 0 else nums1[i - 1] right1 = float("inf") if i == m else nums1[i] left2 = float("-inf") if j == 0 else nums2[j - 1] right2 = float("inf") if j == n else nums2[j]
let left1 = if i == 0 { i32::MIN } else { nums1[i - 1] }; let right1 = if i == m { i32::MAX } else { nums1[i] }; let left2 = if j == 0 { i32::MIN } else { nums2[j - 1] }; let right2 = if j == n { i32::MAX } else { nums2[j] };
const left1 = i === 0 ? -Infinity : nums1[i - 1]; const right1 = i === m ? Infinity : nums1[i]; const left2 = j === 0 ? -Infinity : nums2[j - 1]; const right2 = j === n ? Infinity : nums2[j];
MIN_VALUE means "nothing on the left — always ≤ anything." MAX_VALUE means "nothing on the right — always ≥ anything." This way the cross conditions automatically pass for empty partitions.
Once the partition is valid, the median comes from the boundary values:
class Solution { public double findMedianSortedArrays(int[] nums1, int[] nums2) { // Always binary search on the SMALLER array if (nums1.length > nums2.length) return findMedianSortedArrays(nums2, nums1); int m = nums1.length, n = nums2.length; int lo = 0, hi = m; while (lo <= hi) { int i = (lo + hi) / 2; // partition index in nums1 int j = (m + n + 1) / 2 - i; // partition index in nums2 // Boundary values with sentinel handling int left1 = (i == 0) ? Integer.MIN_VALUE : nums1[i - 1]; int right1 = (i == m) ? Integer.MAX_VALUE : nums1[i]; int left2 = (j == 0) ? Integer.MIN_VALUE : nums2[j - 1]; int right2 = (j == n) ? Integer.MAX_VALUE : nums2[j]; if (left1 <= right2 && left2 <= right1) { // ✓ Valid partition — extract median if ((m + n) % 2 == 1) return Math.max(left1, left2); return (Math.max(left1, left2) + Math.min(right1, right2)) / 2.0; } else if (left1 > right2) { hi = i - 1; // took too many from nums1 } else { lo = i + 1; // took too few from nums1 } } throw new IllegalArgumentException(); } }
func findMedianSortedArrays(nums1 []int, nums2 []int) float64 { // Always binary search on the SMALLER array if len(nums1) > len(nums2) { return findMedianSortedArrays(nums2, nums1) } m, n := len(nums1), len(nums2) lo, hi := 0, m for lo <= hi { i := (lo + hi) / 2 // partition index in nums1 j := (m+n+1)/2 - i // partition index in nums2 // Boundary values with sentinel handling var left1, right1, left2, right2 int if i == 0 { left1 = math.MinInt32 } else { left1 = nums1[i-1] } if i == m { right1 = math.MaxInt32 } else { right1 = nums1[i] } if j == 0 { left2 = math.MinInt32 } else { left2 = nums2[j-1] } if j == n { right2 = math.MaxInt32 } else { right2 = nums2[j] } if left1 <= right2 && left2 <= right1 { // Valid partition — extract median maxLeft := left1 if left2 > maxLeft { maxLeft = left2 } minRight := right1 if right2 < minRight { minRight = right2 } if (m+n)%2 == 1 { return float64(maxLeft) } return float64(maxLeft+minRight) / 2.0 } else if left1 > right2 { hi = i - 1 // took too many from nums1 } else { lo = i + 1 // took too few from nums1 } } return 0.0 }
def find_median_sorted_arrays(nums1: list[int], nums2: list[int]) -> float: # Always binary search on the SMALLER array if len(nums1) > len(nums2): return find_median_sorted_arrays(nums2, nums1) m, n = len(nums1), len(nums2) lo, hi = 0, m while lo <= hi: i = (lo + hi) // 2 # partition index in nums1 j = (m + n + 1) // 2 - i # partition index in nums2 # Boundary values with sentinel handling left1 = float("-inf") if i == 0 else nums1[i - 1] right1 = float("inf") if i == m else nums1[i] left2 = float("-inf") if j == 0 else nums2[j - 1] right2 = float("inf") if j == n else nums2[j] if left1 <= right2 and left2 <= right1: # Valid partition — extract median if (m + n) % 2 == 1: return max(left1, left2) return (max(left1, left2) + min(right1, right2)) / 2 elif left1 > right2: hi = i - 1 # took too many from nums1 else: lo = i + 1 # took too few from nums1 raise ValueError("Invalid input")
impl Solution { pub fn find_median_sorted_arrays(nums1: Vec<i32>, nums2: Vec<i32>) -> f64 { // Always binary search on the SMALLER array if nums1.len() > nums2.len() { return Solution::find_median_sorted_arrays(nums2, nums1); } let m = nums1.len(); let n = nums2.len(); let mut lo: i32 = 0; let mut hi: i32 = m as i32; while lo <= hi { let i = ((lo + hi) / 2) as usize; // partition index in nums1 let j = (m + n + 1) / 2 - i; // partition index in nums2 // Boundary values with sentinel handling let left1 = if i == 0 { i32::MIN } else { nums1[i - 1] }; let right1 = if i == m { i32::MAX } else { nums1[i] }; let left2 = if j == 0 { i32::MIN } else { nums2[j - 1] }; let right2 = if j == n { i32::MAX } else { nums2[j] }; if left1 <= right2 && left2 <= right1 { // Valid partition — extract median let max_left = left1.max(left2); let min_right = right1.min(right2); if (m + n) % 2 == 1 { return max_left as f64; } return (max_left as f64 + min_right as f64) / 2.0; } else if left1 > right2 { hi = i as i32 - 1; // took too many from nums1 } else { lo = i as i32 + 1; // took too few from nums1 } } 0.0 } }
function findMedianSortedArrays(nums1: number[], nums2: number[]): number { // Always binary search on the SMALLER array if (nums1.length > nums2.length) return findMedianSortedArrays(nums2, nums1); const m = nums1.length, n = nums2.length; let lo = 0, hi = m; while (lo <= hi) { const i = Math.floor((lo + hi) / 2); // partition index in nums1 const j = Math.floor((m + n + 1) / 2) - i; // partition index in nums2 // Boundary values with sentinel handling const left1 = i === 0 ? -Infinity : nums1[i - 1]; const right1 = i === m ? Infinity : nums1[i]; const left2 = j === 0 ? -Infinity : nums2[j - 1]; const right2 = j === n ? Infinity : nums2[j]; if (left1 <= right2 && left2 <= right1) { // Valid partition — extract median if ((m + n) % 2 === 1) return Math.max(left1, left2); return (Math.max(left1, left2) + Math.min(right1, right2)) / 2; } else if (left1 > right2) { hi = i - 1; // took too many from nums1 } else { lo = i + 1; // took too few from nums1 } } throw new Error("Invalid input"); }
Try different inputs and step through the binary search iteration by iteration.
We binary search on the partition index i in the smaller array. The search space is [0, min(m, n)], so it takes at most log(min(m, n)) iterations to converge. Each iteration does O(1) work: compute j, read four boundary values, and compare two cross conditions. No auxiliary arrays or data structures are allocated — just a handful of integer variables.
Two pointers merge both sorted arrays into a single sorted array of length m + n, visiting every element exactly once. The median is then read directly from the middle index. The merged array requires O(m + n) auxiliary storage.
Binary search on the partition index i of the smaller array halves the search space each iteration. The complementary index j is computed directly, and only four boundary values are checked per step -- all O(1) work. Only a handful of integer variables are used, requiring no extra arrays.
We binary search partitions, not elements. Each step eliminates half of the smaller array's candidates. The problem asks for O(log(m+n)), but by always searching the smaller array, we achieve O(log(min(m, n))) — strictly better when one array is much larger than the other.
Review these before coding to avoid predictable interview regressions.
Wrong move: Setting `lo = mid` or `hi = mid` can stall and create an infinite loop.
Usually fails on: Two-element ranges never converge.
Fix: Use `lo = mid + 1` or `hi = mid - 1` where appropriate.