Let X[1..n] and Y[1..n] be two arrays, each containing n numbers already in sorted order. Give an O(lgn)-time algorithm to find the median of all 2n elements in arrays X and Y.

Find the median.c

//

//from 'introduce to algorithm'
//Precondition: the length of seq1 is equal to seq2, both of them are n.
  7 int findMed(int seq1[], int seq2[], int n, int low, int high){
  8     if (low > high)
  9             return -1;
 10     int k = (high + low)/2;
 11     if (k == n-1 && seq1[n-1]<=seq2[0])
 12             return seq1[n-1];
 13     else if(k < n-1 && seq1[k] >= seq2[n-k-1] && seq1[k] <= seq2[n-k])
 14             return seq1[k];
 15     else if(seq1[k] > seq2[n-k])
 16             return findMed(seq1, seq2, n, low, k-1);
 17     else
 18             return findMed(seq1, seq2, n, k+1, high);
 19 }
 20
 21 int two_array_median(int seq1[], int seq2[], int len){
 22     int med = findMed(seq1, seq2, len, 0, len-1);
 23     if (med == -1)
 24             return findMed(seq1, seq2, len, 0, len-1);
 25     else
 26             return med;
 27 }


 29 //two arrays with different length
    //Assume the median of array A is m and the median of array B is n.
    //1' If m=n, then clearly the median after merging is also m, the algorithm holds.
    //2' If m<n, then reserve the half of sequence A in which all numbers are greater than m, also reserve the half of sequence B in which all            numbers are smaller than n. Run the algorithm on the two new arrays.
    //3' If m>n, then reserve the half of sequence A in which all numbers are smaller than m, also reserve the half of sequence B in which all numbers are larger than n. Run the algorithm on the two new arrays.

 30 int findMedian(int arr1[], int arr2[], int len1, int len2){
 31     int begin1 = 0, end1 = len1 - 1;
 32     int begin2 = 0, end2 = len2 - 1;
 33     int med1 = (len1%2)?(len1/2):(len1/2 - 1);
 34     int med2 = (len2%2)?(len2/2):(len2/2 - 1);
 35
 36     //arr1 is null
 37     if (end1 < begin1){
 38         return arr2[med2];
 39     }
 40
 41     //arr2 is null
 42     if (end2 < begin2){
 43         return arr1[med1];
 44     }
 45
 46     if (arr1[med1] == arr2[med2])
 47         return arr1[med1];
 48
 49     //there is only one element in arr1, and the length of arr2 is odd
 50     if (begin1 == end1 && len2 > 1 &&len2%2){
 51         if (arr1[med1] > arr2[med2]){
 52             return arr2[med2];
 53         }
 54     }
 55
 56     //there is only one element in arr1, and the length of arr2 is even.
 57     if (begin1 == end1 && len2 && len2%2 == 0){
 58         if (arr1[med1]>arr2[med2] && arr1[med1] < arr2[med2+1]){
 59             return arr1[med1];
 60         }
 61     }
 62     //there is only one element in arr2, and the length of arr1 is odd.
 63     if (begin2 == end2 && len1 > 1 &&len1%2){
 64         if (arr2[med2] > arr1[med1]){
 65             return arr1[med1];
 66         }
 67     }
 68     //there is only one element in arr2, and the length of arr1 is even.
 69     if (begin2 == end2 && len1 && len1%2 == 0){
 70         if (arr2[med2] > arr1[med1] && arr2[med2] < arr1[med2+1])
 71             return arr2[med2];
 72     }
 73
 74     int offset = 0;
 75     if (arr1[med1] > arr2[med2]){
 76         offset = ((med1 - begin1) > (end2 - med2))? (end2 - med2):(med1 - begin1);
 77         findMedian(arr1+med1-offset, arr2+med2, offset, offset);
 78     }else {
 79         offset = ((end1 - med1) > (med2 - begin2))? (med2 - begin2):(end1 - med1);
 80         findMedian(arr1+med1, arr2+med2-offset, offset, offset);
 81     }
 82 }