whew okay this one is wayy over my head... if someone actually can answer this,

Question

whew okay this one is wayy over my head... if someone actually can answer this, i'll be more than grateful

Let X(1..n) and Y(1..n) contain two lists of integers, each sorted in nondecreasing order. Give an O(log n)-time algorithm to find the median (or the nth smallest integer) of all 2n combined elements. For ex, X = (4, 5, 7, 8, 9) and Y = (3, 5, 8, 9, 10), then 7 is the median of the combined list (3, 4, 5, 5, 7, 8, 8, 9, 9, 10). [Hint: use concepts of binary search]

Explanation / Answer

Hi, hope this will help u PLEASE RATE Median: In probability theory and statistics, a median is described as the number separating the higher half of a sample, a population, or a probability distribution, from the lower half. The median of a finite list of numbers can be found by arranging all the numbers from lowest value to highest value and picking the middle one. For getting the median of input array { 12, 11, 15, 10, 20 }, first sort the array. We get { 10, 11, 12, 15, 20 } after sorting. Median is the middle element of the sorted array which is 12. There are different conventions to take median of an array with even number of elements, one can take the mean of the two middle values, or first middle value, or second middle value. Let us see different methods to get the median of two sorted arrays of size n each. Since size of the set for which we are looking for median is even (2n), we are taking average of two middle two numbers in all below solutions. Method 1 (Simply count while Merging) Use merge procedure of merge sort. Keep track of count while comparing elements of two arrays. If count becomes n(For 2n elements), we have reached the median. Take the average of the elements at indexes n-1 and n in the merged array. See the below implementation. Implementation: /* This function returns median of ar1[] and ar2[]. Assumptions in this function: Both ar1[] and ar2[] are sorted arrays Both have n elements */ int getMedian(int ar1[], int ar2[], int n) { int i = 0; /* Current index of i/p array ar1[] */ int j = 0; /* Current index of i/p array ar2[] */ int count; int m1 = -1, m2 = -1; /* Since there are 2n elements, median will be average of elements at index n-1 and n in the array obtained after merging ar1 and ar2 */ for(count = 0; count right) return getMedianRec(ar2, ar1, 0, n-1, n); i = (left + right)/2; j = n – i – 1; /* Index of ar2[] */ /* Recursion terminates here.*/ if(ar1[i] > ar2[j] && (j == n-1 || ar1[i] ar1[i-1] || i == 0) return (ar1[i] + ar2[j])/2; else return (ar1[i] + ar1[i-1])/2; } /*Search in left half of ar1[]*/ else if (ar1[i] > ar2[j] && j != n-1 && ar1[i] > ar2[j+1]) return getMedianRec(ar1, ar2, left, i-1, n); /*Search in right half of ar1[]*/ else /* ar1[i] is smaller than both ar2[j] and ar2[j+1]*/ return getMedianRec(ar1, ar2, i+1, right, n); } /* Driver program to test above function */ int main() { int ar1[] = {1, 12, 15, 26, 38}; int ar2[] = {2, 13, 17, 30, 45}; printf(“%d”, getMedian(ar1, ar2, 5)) ; getchar(); return 0; } Time Complexity: O(logn) Space Complexity: O(1) Algorithmic Paradigm: Divide and Conquer

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.