Introduction
The problem of finding the median of two sorted arrays is a classic coding interview question. The challenge is to find the median efficiently, with a time complexity of O(log(min(m, n))), where m and n are the sizes of the two arrays. In this article, we’ll walk through a Java solution that employs binary search to achieve this efficiency.
Problem Statement
Given two sorted arrays nums1 and nums2, find the median of the two sorted arrays. The overall runtime complexity should be O(log(min(m, n))), where m and n are the sizes of the two arrays.
Approach
To solve this problem, we use a binary search approach on the smaller of the two arrays. The goal is to partition both arrays such that the left half contains all elements less than or equal to the elements in the right half. Here’s a step-by-step explanation:
-
Ensure
nums1is the Smaller Array: For easier binary search, make surenums1is the smaller array. -
Perform Binary Search: Use binary search on
nums1to find the correct partition. - Partitioning: Partition both arrays such that the left side contains lower elements, and the right side contains higher elements.
- Calculate Median: Based on the partitions, calculate the median.
Solution
Here’s a detailed Java implementation of the solution:
public class MedianOfTwoSortedArrays {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
// Ensure nums1 is the smaller array
if (nums1.length > nums2.length) {
int[] temp = nums1;
nums1 = nums2;
nums2 = temp;
}
int x = nums1.length;
int y = nums2.length;
int low = 0, high = x;
while (low <= high) {
int partitionX = (low + high) / 2;
int partitionY = (x + y + 1) / 2 - partitionX;
// Edge cases
int maxX = (partitionX == 0) ? Integer.MIN_VALUE : nums1[partitionX - 1];
int minX = (partitionX == x) ? Integer.MAX_VALUE : nums1[partitionX];
int maxY = (partitionY == 0) ? Integer.MIN_VALUE : nums2[partitionY - 1];
int minY = (partitionY == y) ? Integer.MAX_VALUE : nums2[partitionY];
if (maxX <= minY && maxY <= minX) {
// Correct partition
if ((x + y) % 2 == 0) {
return (Math.max(maxX, maxY) + Math.min(minX, minY)) / 2.0;
} else {
return Math.max(maxX, maxY);
}
} else if (maxX > minY) {
high = partitionX - 1;
} else {
low = partitionX + 1;
}
}
throw new IllegalArgumentException("Input arrays are not sorted");
}
public static void main(String[] args) {
MedianOfTwoSortedArrays solution = new MedianOfTwoSortedArrays();
int[] nums1 = {1, 3};
int[] nums2 = {2};
System.out.println("Median: " + solution.findMedianSortedArrays(nums1, nums2)); // Output: 2.0
int[] nums1_2 = {1, 2};
int[] nums2_2 = {3, 4};
System.out.println("Median: " + solution.findMedianSortedArrays(nums1_2, nums2_2)); // Output: 2.5
}
}
Explanation
-
Initialization: Ensure
nums1is the smaller array. -
Binary Search: Perform binary search on
nums1to find the correct partition. - Partitioning and Median Calculation: Calculate the maximum of the left elements and the minimum of the right elements to find the median.
Conclusion
This binary search approach provides an efficient solution to finding the median of two sorted arrays. By leveraging binary search on the smaller array, the solution achieves a time complexity of O(log(min(m, n))), making it suitable for large input arrays.
Top comments (0)