The median of a set of n numbers is the number that is bigge

The median of a set of n numbers is the number that is bigger (or smaller) than half the numbers. The median does not have to be unique. Given two sorted arrays A and B of size n each. Describe an algorithm to find the median of the 2n numbers in A and B. The complexity should be O(log(n)). Explain your answer. There is no need to write code, just describe your method.

Hint: Use recursion, not unlike a recursive search.

Solution

Algorithm to merge two sorted array in O(logn) time

=> Determine the median median1 and median2 of both the sorted arrays array1[] and array2[] respectively.

=> Check if the medians median1 and median2 are equal then we get the result. return any one of the medians.

=> If median1 is greater than median2, then median is present in one of the two subarrays given below
    => From start element of array1 to median1 (array1[0...|n/2|])
    => From median2 to end element of array2 (array2[|n/2|...n-1])

=> If median2 is greater than median1, then median is present in one of the two subarrays given below
   => From median1 to end element of array1 (array1[|n/2|...n-1])
   => From start element of array2 to median2 (array2[0...|n/2|])

=> Repeating the same process until size of both the subarrays becomes 2.

//Recursive method:
int recursiveMedian(int array1[], int array2[], int n)
{
    // base cases
    if (n == 1)
        return (array1[0] + array2[0])/2;
    else if (n == 2)
        return (max(array1[0], array2[0]) + min(array1[1], array2[1])) / 2;
  
    // Determine the median median1 and median2 of both the sorted arrays array1[] and array2[] respectively
    int median1 = median(array1, n);
    int median2 = median(array2, n);
  
    // Check if the medians median1 and median2 are equal then we get the result. return any one of the medians.
    if (median1 == median2)
        return median1;
  
    /*
    If median2 is greater than median1, then median is present in one of the two subarrays given below
      => From median1 to end element of array1 (array1[|n/2|...n-1])
      => From start element of array2 to median2 (array2[0...|n/2|])
   */
    if (median1 < median2)
    {
        if (n % 2 == 0)
            // recursive call to get median, incrementing index of array1 and decreasing size
            return recursiveMedian(array1 + n/2 - 1, array2, n - n/2 +1);
        // recursive call to get median, incrementing index of array1 and decreasing size
        return recursiveMedian(array1 + n/2, array2, n - n/2);
    }
  
    /*
    If median1 is greater than median2, then median is present in one of the two subarrays given below
      => From start element of array1 to median1 (array1[0...|n/2|])
      => From median2 to end element of array2 (array2[|n/2|...n-1])
    */
    if (n % 2 == 0)
        // recursive call incrementing index of array2 and decreasing size
        return recursiveMedian(array2 + n/2 - 1, array1, n - n/2 + 1);
    // recursive call incrementing index of array2 and decreasing size
    return recursiveMedian(array2 + n/2, array1, n - n/2);
}

// determine median of array
int median(int array[], int size)
{
    if (size%2 == 0)
        return (array[size/2] + array[size/2-1])/2;
    else
        return array[size/2];
}