Median of Two Sorted Arrays
Solve median-of-two-sorted-arrays in O(log(min(m,n))) using binary search on the partition boundary of the shorter array.
The Median of Two Sorted Arrays
Median of Two Sorted Arrays (LeetCode 4) is a classic hard problem. Given two sorted arrays nums1 (length m) and nums2 (length n), find the median of their combined sorted sequence in O(log(min(m,n))) time. A naive approach merges both arrays in O(m+n), but the optimal solution uses binary search on partition boundaries. This is one of the most frequently asked hard problems at top tech companies.
# Examples:
nums1 = [1, 3]
nums2 = [2]
# Combined sorted: [1, 2, 3] → median = 2.0
nums1b = [1, 2]
nums2b = [3, 4]
# Combined sorted: [1, 2, 3, 4] → median = (2+3)/2 = 2.5
print('Example 1 median:', 2.0)
print('Example 2 median:', 2.5)
print('Total length:', len(nums1)+len(nums2), 'and', len(nums1b)+len(nums2b))Naive Merge Approach
The simplest O(m+n) approach: merge both sorted arrays, then find the median. Merging two sorted arrays is O(m+n). The median of an array of length L is arr[L//2] if L is odd, or (arr[L//2-1] + arr[L//2]) / 2 if L is even. This is correct but does not meet the O(log(min(m,n))) requirement. Always present this first in an interview to establish a baseline, then optimise.
def find_median_naive(nums1, nums2):
# Merge two sorted arrays
merged = []
i = j = 0
while i < len(nums1) and j < len(nums2):
if nums1[i] <= nums2[j]:
merged.append(nums1[i]); i += 1
else:
merged.append(nums2[j]); j += 1
merged += nums1[i:] + nums2[j:]
L = len(merged)
if L % 2 == 1:
return float(merged[L // 2])
return (merged[L//2 - 1] + merged[L//2]) / 2.0
print(find_median_naive([1,3],[2])) # 2.0
print(find_median_naive([1,2],[3,4])) # 2.5All lessons in this course
- Divide and Conquer Template
- Count Inversions Using Modified Merge Sort
- Majority Element: Boyer-Moore Voting
- Median of Two Sorted Arrays