4. Let A and B be two sorted arrays, each array consists of n real numbers in as
ID: 3756831 • Letter: 4
Question
4. Let A and B be two sorted arrays, each array consists of n real numbers in ascending order. Give an algorithm, running in O(log n) time, to compute the median of the elements formed by the union of the elements in both the arrays. (You may assume that the union consists of 2n distinct real numbers.) Hint: Assume that the median en forT 2 to be the median element, you can say something about how many elements in B need to smaller than r and that can be checked in O(1) time. The problem to solve here is how fast you element is from A, and assume that it is at index i. Then forAli to be the median can searc or T inExplanation / Answer
class Main
{
static int getMedian(int ar1[], int ar2[], int n)
{
int i = 0;
int j = 0;
int count;
int m1 = -1, m2 = -1;
for (count = 0; count <= n; count++)
{
if (i == n)
{
m1 = m2;
m2 = ar2[0];
break;
}
else if (j == n)
{
m1 = m2;
m2 = ar1[0];
break;
}
if (ar1[i] < ar2[j])
{
/* Store the prev median */
m1 = m2;
m2 = ar1[i];
i++;
}
else
{
m1 = m2;
m2 = ar2[j];
j++;
}
}
return (m1 + m2)/2;
}
public static void main (String[] args)
{
int ar1[] = {1, 9, 10, 26, };
int ar2[] = {2, 13, 17, 30, };
int l1 = ar1.length;
int l2 = ar2.length;
if (l1 == l2)
System.out.println("Median is " +
getMedian(ar1, ar2, l1));
else
System.out.println("arrays are of unequal size");
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.