Medianof Two Sorted Arrays Algorithm
The Median of Two Sorted Arrays Algorithm is an efficient technique used to find the median element(s) from two given sorted arrays. This algorithm is essential in solving various computational problems, such as finding the middle value in a combined dataset, which is crucial in determining a central tendency for a set of data. The primary goal of this algorithm is to find the median value in the most time-efficient manner, often achieving a complexity of O(log(min(m, n))), where m and n are the sizes of the two arrays.
The algorithm works by dividing the two arrays into two equal parts, such that the maximum element in the left half is less than or equal to the minimum element in the right half. To achieve this, the algorithm performs a binary search on the smaller array, dividing it into two parts. Then, based on the position of the partition in the smaller array, a partition is performed on the larger array as well. After the partitions are done, the algorithm compares the elements around the partition to ensure the condition that the maximum element in the left half is less than or equal to the minimum element in the right half. If the condition is not met, the algorithm continues with the binary search, adjusting the partitions accordingly. Once the condition is met, the median can be computed by considering the elements around the partition.
class Solution {
public:
double findMedianSortedArrays(int A[], int m, int B[], int n) {
if ((m + n) & 1) {
return findKth((m + n - 1) / 2, A, 0, m - 1, B, 0, n - 1);
} else {
int x = findKth((m + n) / 2 - 1, A, 0, m - 1, B, 0, n - 1);
int y = findKth((m + n) / 2, A, 0, m - 1, B, 0, n - 1);
return (x + y) / 2.0;
}
}
int findKth(int k, int A[], int l1, int r1, int B[], int l2, int r2) {
if (l1 > r1) {
return B[l2 + k];
}
if (l2 > r2) {
return A[l1 + k];
}
int m1 = (l1 + r1) / 2;
int m2 = (l2 + r2) / 2;
if (A[m1] > B[m2]) {
if (k + 1 < m1 - l1 + 1 + m2 - l2 + 1) {
return findKth(k, A, l1, m1 - 1, B, l2, r2);
} else {
return findKth(k - (m2 - l2 + 1), A, l1, r1, B, m2 + 1, r2);
}
} else {
if (k + 1 < m1 - l1 + 1 + m2 - l2 + 1) {
return findKth(k, A, l1, r1, B, l2, m2 - 1);
} else {
return findKth(k - (m1 - l1 + 1), A, m1 + 1, r1, B, l2, r2);
}
}
}
};
