LeetEye LeetEye
Medium Binary Search ~5 min

Median of Two Sorted Arrays

binary-search median-of-two-sorted-arrays

Problem

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)).

Examples

Example 1
Input: nums1 = [1,3], nums2 = [2]
Output: 2.0
merged = [1,2,3], median = 2
Example 2
Input: nums1 = [1,2], nums2 = [3,4]
Output: 2.5
merged = [1,2,3,4], median = (2+3)/2 = 2.5
Key Insight

Binary search for a partition: split both arrays such that left partition has exactly half the total elements, and all left elements ≤ all right elements.

Binary search partition point in smaller array. Valid partition: max(left_halves) ≤ min(right_halves). Median from partition boundaries.

How to Approach This Problem

Pattern Recognition: When you see keywords like median of two sorted arrays binary-search, think Binary Search.

Step-by-Step Reasoning

1 For n elements, the median is:
Answer: Middle element (odd n) or average of two middle (even n)
Median = value that separates the higher half from lower half.
2 For total = m + n elements, the left partition should contain:
Answer: (m + n + 1) / 2 elements
For odd total, include the median in left. For even total, this equals half. Works for both.
3 If we take i elements from nums1 for left partition, from nums2 we take:
Answer: half - i elements
Total left = half = i + j, so j = half - i.
4 A partition is valid when:
Answer: nums1[i-1] ≤ nums2[j] AND nums2[j-1] ≤ nums1[i]
max(left of nums1) ≤ min(right of nums2), AND max(left of nums2) ≤ min(right of nums1). This ensures left ≤ right overall.
5 If nums1[i-1] > nums2[j], we should:
Answer: Decrease i (take fewer from nums1)
nums1's left side has an element too large. Move partition left in nums1 to reduce it.
6 We binary search on the smaller array because:
Answer: Ensures j = half - i is always valid (non-negative)
If we search on larger array, i might be so large that j becomes negative. Searching smaller ensures 0 ≤ j ≤ n.

Solution

def findMedianSortedArrays(nums1: List[int], nums2: List[int]) -> float:
    # Ensure nums1 is smaller
    if len(nums1) > len(nums2):
        nums1, nums2 = nums2, nums1
    
    m, n = len(nums1), len(nums2)
    half = (m + n + 1) // 2
    left, right = 0, m
    
    while left <= right:
        i = (left + right) // 2  # Partition in nums1
        j = half - i              # Partition in nums2
        
        left1 = nums1[i-1] if i > 0 else float(&#039;-inf')
        right1 = nums1[i] if i < m else float(&#039;inf')
        left2 = nums2[j-1] if j > 0 else float(&#039;-inf')
        right2 = nums2[j] if j < n else float(&#039;inf')
        
        if left1 <= right2 and left2 <= right1:
            # Valid partition
            if (m + n) % 2 == 1:
                return max(left1, left2)
            return (max(left1, left2) + min(right1, right2)) / 2
        elif left1 > right2:
            right = i - 1
        else:
            left = i + 1
    
    return 0.0

Complexity Analysis

Time O(log(min(m,n)))
Space O(1)

Master This Pattern

Build intuition with interactive MCQs. Practice Binary Search problems in the LeetEye app.

Download LeetEye Free
Practice in LeetEye