Question 1: Let A and B be two sorted arrays of n elements each (thus A + B has
ID: 3881275 • Letter: Q
Question
Question 1: Let A and B be two sorted arrays of n elements each (thus A + B has 2·n elements in total). Give an algorithm that finds the median of A B . This is a number that is larger and equal of half the elements, and is strictly smaller than half of the elements.
Remark: For simplicity assume that every value appears at most once in A B.
Example: A = < 2 ,7 , 19 , 22 > B = <6 , 17 , 24 , 25 > The number 17 is at least as large as <2 , 6 ,7 , 17 > and smaller than < 19 , 22 , 25 , 25 > Hint: There is a very fast algorithm for this task.
Explanation / Answer
Hi.. I have written a program to achive the above. Please check below code.
MedianAlgo.java
class MedianAlgo
{
static void calculate(int ar1[], int ar2[], int n)
{
int arr[] = new int[n+n];
int c=0;
for(int i=0;i<n;i++)
arr[i]=ar1[i];
for(int i=0;i<n;i++)
arr[i+n]=ar2[i];
int max = n+n;
for (int i = 0; i < max; i++)
{
for (int j = i + 1; j < max; j++)
{
if (arr[i] > arr[j])
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
}
int m = max/2;
int median = arr[m-1];
//int median = m1>m2?m1:m2;
int largestthan[] = new int[n];
int smallestthan[] = new int[n];
int count1 = 0;
int count2=0;
for(int k=0;k<n;k++){
if(ar1[k]<=median){
largestthan[count1] = ar1[k];
count1++;
}else{
smallestthan[count2] = ar1[k];
count2++;
}
}
for(int k=0;k<n;k++){
if(ar2[k]<=median){
largestthan[count1] = ar2[k];
count1++;
}else{
smallestthan[count2] = ar2[k];
count2++;
}
}
if(count1!=n){
largestthan[n-1]=largestthan[count1-1];
}else if(count2!=n){
smallestthan[n-1]=smallestthan[count1-1];
}
System.out.println("Median is:"+median);
System.out.print("large as <");
for(int k=0;k<n;k++){
System.out.print(largestthan[k]+",");
}
System.out.println(">");
System.out.print("smaller than <");
for(int k=0;k<n;k++){
System.out.print(smallestthan[k]+",");
}
System.out.println(">");
//return m1>m2?m1:m2;
}
public static void main (String[] args)
{
int ar1[] = {2,7,19,22};
int ar2[] = {6,18,24,25};
int n1 = ar1.length;
int n2 = ar2.length;
if (n1 == n2)
calculate(ar1, ar2, n1);
else
System.out.println("arrays are of unequal size");
}
}
Output:
Median is:18
large as <2,7,6,18,>
smaller than <19,22,24,25,>
Please check the code and let me know any issues. Thank you. All the best.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.