Find the median of two positive sequence arrays
First, let’s understand the definition of median. The median is the number in the middle of the sorted array, or the average of the two middle numbers if the length of the array is even. For two ordinal arrays, we need to find their median.
First, let’s look at a simple example. Suppose we have two arrays
nums1 = [1, 3] nums2 = [2]
We need to combine them into a sorted array
merged = [1, 2, 3]
We can then find the median of this sorted array
median = 2
This is a relatively simple problem, merging two arrays and sorting them requires O(n log n) time complexity, where n is the sum of the lengths of the two arrays. However, there is a more efficient solution to this problem that requires O(log (m + n)) time complexity, where m and n are the lengths of the two arrays respectively. This method is called binary search. Next, we’ll take a closer look at how to use binary search to find the median of two ordinal arrays.
Transform the problem into finding the kth element
To find the median of two sorted arrays, you first need to understand how to find the kth element of a sorted array.
Suppose we have two positive sequence arrays ?nums1? and ?nums2, and their lengths are ?m? and ?n , we need to find the ?k?th element in the sorted array after the combination of these two arrays, where?1 <= k <= m + n.
We can define ?i? and ?j? to point to ?nums1? and ?nums2? The starting position of the array, and then compare?nums1[i]? and?nums2[j], move the pointer to the array with the smaller value back one position, This process is repeated until the ?k?th element of the sorted array is found. It can be expressed as the following pseudocode.
int i = 0, j = 0, k;
for (k = 1; k < kth; k ++ ) {
if (i == m) j ++ ;
else if (j == n) i ++ ;
else if (nums1[i] < nums2[j]) i + + ;
else j ++ ;
}
int kth_elem = (i == m) ? nums2[j] : (j == n) ? nums1[i] : Math.min(nums1[i], nums2[j]);
In the above pseudocode, kth? indicates the kth element of the sorted array to be found.
Next, we'll optimize this algorithm using binary search.
Use binary search
The idea of binary search is to divide a larger problem into two smaller but similarly structured sub-problems, then recursively solve these sub-problems, and finally combine the results. We can turn the problem into finding the ?(m + n)/2?th element of a sorted array, if the length of the array is even, we need to find the ?(m + n)th element Average of /2? and ?(m + n)/2 + 1? elements.
We can define two pointers?p1? and?p2? point to?nums1? and?nums2 respectively ? The starting position. We need to find the values pointed to by the two pointers of ?p1? and ?p2? respectively after moving ?k/2? ?mid1? and ?mid2. If ?mid1? is less than ?mid2, then the median is located between ?nums1[p1,...]? and ? nums2[...p2]?, because ?nums1[0,...,p1-1]? must be smaller than ?mid1, and ?nums2[0,...,p2-1]? must be less than?mid1. Therefore, we need to shift ?p1? to the right by?(k + 1)/2? positions.
At this point, we compare ?mid1? with ?mid2? again, and repeat the above operations until we find the ?(m + n)/2 of the sorted array ? elements. In implementation, we need to pay special attention to the following situations.
- One array may be shorter than the other.
- Array may be empty.
According to the above situation, we can define the following two auxiliary functions.
// Find the kth element in array A and array B
public int findKth(int
// Find the kth element in array A and array B
public int findKth(int[] A, int i, int[] B, int j, int k) {<!-- -->
// When the A array is empty, directly return the kth element of the B array
if (i >= A.length) return B[j + k - 1];
// When the B array is empty, directly return the kth element of the A array
if (j >= B.length) return A[i + k - 1];
// When k is equal to 1, return the minimum value of the two arrays
if (k == 1) return Math.min(A[i], B[j]);
// Find the k/2th element of the A array and the k/2th element of the B array respectively
int mid1 = (i + k/2 - 1 < A.length) ? A[i + k/2 - 1] : Integer.MAX_VALUE;
int mid2 = (j + k/2 - 1 < B.length) ? B[j + k/2 - 1] : Integer.MAX_VALUE;
// If mid1 is less than mid2, the median is between nums1[p1,...] and nums2[...p2]
if (mid1 < mid2)
return findKth(A, i + k/2, B, j, k - k/2);
else return findKth(A, i, B, j + k/2, k - k/2); }
// find the median of array A and array B
public double findMedianSortedArrays(int[] A, int[] B) {<!-- --> int m = A.length, n = B.length; int k = (m + n) / 2;
// If the sum of the array lengths is an odd number, return the k + 1th element directly if ((m + n) % 2 == 1) return findKth(A, 0, B, 0, k + 1);
// If the sum of the lengths of the array is even, return the average of the kth element and the k+1th element
else
return (findKth(A, 0, B, 0, k) + findKth(A, 0, B, 0, k + 1)) / 2.0; }
Now, we have mastered binary search in Java to find the median of two ordinal arrays. Next, we'll use some examples to demonstrate how to use it in real problems.
Example
Example 1
enter:
nums1 = [1, 3] nums2 = [2]
output:
2.0
Explanation: The merged sorted array is [1, 2, 3] with a median of 2.
int[] nums1 = {<!-- -->1, 3};
int[] nums2 = {<!-- -->2};
Solution solution = new Solution();
double result = solution.findMedianSortedArrays(nums1, nums2);
System.out.println(result); // 2.0
Example 2
enter:
nums1 = [1, 2] nums2 = [3, 4]
output:
2.5
Explanation: The merged sorted array is ?[1, 2, 3, 4], and the median is ?(2 + 3) / 2 = 2.5.
int[] nums1 = {1, 2};
int[] nums2 = {3, 4};
Solution solution = new Solution();
double result = solution.findMedianSortedArrays(nums1, nums2);
System.out.println(result); // 2.5
Copy
Example 3
enter:
nums1 = [0, 0] nums2 = [0, 0]
output:
0.0
Explanation: The merged sorted array is ?[0, 0, 0, 0], and the median is ?(0 + 0) / 2 = 0.0.
int[] nums1 = {0, 0};
int[] nums2 = {0, 0};
Solution solution = new Solution();
double result = solution.findMedianSortedArrays(nums1, nums2);
System.out.println(result); // 0.0
Summary
This article discusses how to use binary search to find the median of two ordinal arrays. We converted the problem to find the ?k?th element of a sorted array, then used binary search to optimize the algorithm, and finally achieved a faster time complexity. Finally, we use a few examples to illustrate how this algorithm can be used in real problems.