Algorithms - Median of 2 sorted arrays Let A and B be sorted arrays of n element
ID: 668604 • Letter: A
Question
Algorithms - Median of 2 sorted arrays
Let A and B be sorted arrays of n elements each. We can easily find the median of A or the median of B, since they are already sorted – it will be at index floor(n+1/2). But what if we want to find the median element of A B? We could just concatenate them and use the O(n) time median algorithm, but is it possible to do better? In this problem you should give matching upper and lower bounds, i.e. you should find a function f(n) and do the following:
(a) Design a deterministic algorithm whose running time (measured in terms of the number of comparisons) is O(f(n)), and
(b) Give a lower bound showing that any comparison-based algorithm must make (f(n)) comparisons in the worst case.
I have no idea how to approach this. I would make a decision tree for (b) but I'm really stuck. How do I make a deterministic algorithm
Explanation / Answer
Program :
double findMedianBaseCase(int med, int C[], int n)
{
if (n == 1)
return (med+C[0])/2.0;
if (n % 2 == 0)
{
int a = C[n/2 - 1], b = C[n/2];
if (med <= a)
return a;
else if (med <= b)
return med;
else /* med > b */
return b;
}
else
{
int a = C[n/2 - 1], b = C[n/2], c = C[n/2 + 1];
if (med <= a)
return (a+b) / 2.0;
else if (med <= c)
return (med+b) / 2.0;
else /* med > c */
return (b+c) / 2.0;
}
}
double findMedianBaseCase2(int med1, int med2, int C[], int n) {
if (n % 2 == 0) {
int a = (((n/2-2) >= 0) ? C[n/2 - 2] : INT_MIN);
int b = C[n/2 - 1], c = C[n/2];
int d = (((n/2 + 1) <= n-1) ? C[n/2 + 1] : INT_MAX);
if (med2 <= b)
return (b+max(med2,a)) / 2.0;
else if (med1 <= b)
return (b+min(med2,c)) / 2.0;
else if (med1 >= c)
return (c+min(med1,d)) / 2.0;
else if (med2 >= c)
return (c+max(med1,b)) / 2.0;
else /* a < med1 <= med2 < b */
return (med1+med2) / 2.0;
}
else
{
int a = C[n/2 - 1], b = C[n/2], c = C[n/2 + 1];
if (med1 >= b)
return min(med1, c);
else if (med2 <= b)
return max(med2, a);
else /* med1 < b < med2 */
return b;
}
}
double findMedianSingleArray(int A[], int n)
{
assert(n > 0);
return ((n%2 == 1) ? A[n/2] : (A[n/2-1]+A[n/2])/2.0);
}
double findMedianSortedArrays(int A[], int m, int B[], int n) {
assert(m+n >= 1);
if (m == 0)
return findMedianSingleArray(B, n);
else if (n == 0)
return findMedianSingleArray(A, m);
else if (m == 1)
return findMedianBaseCase(A[0], B, n);
else if (n == 1)
return findMedianBaseCase(B[0], A, m);
else if (m == 2)
return findMedianBaseCase2(A[0], A[1], B, n);
else if (n == 2)
return findMedianBaseCase2(B[0], B[1], A, m);
int i = m/2, j = n/2, k;
if (A[i] <= B[j])
{
k = ((m%2 == 0) ? min(i-1, n-j-1) : min(i, n-j-1));
assert(k > 0);
return findMedianSortedArrays(A+k, m-k, B, n-k);
}
else
{
k = ((n%2 == 0) ? min(m-i-1, j-1) : min(m-i-1, j));
assert(k > 0);
return findMedianSortedArrays(A, m-k, B+k, n-k);
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.