Find median of two sorted arrays

Given two sorted arrays a and b each of size 'n', find the median of the array obtained by merging these two arrays.
For example - for following two arrays 'a' and b',  
a = 1, 3, 5, 11, 17  b = 9, 10, 11, 13, 14   Sorted(a+b) = 1, 3, 5, 9, 10, 11, 11, 13, 14, 17 and therefore Median = (10 + 11)/2 => 10.5
output returned should be 10.5.


Please try solving this problem before jumping on the solution

Click to learn






Subscribe for more updates



Algorithm/Insights

If array 'a' and 'b' both are of size 'n' and are sorted then to find out the median of new array obtained by merging 'a' and 'b', following algorithm is used -
1. Base Case - If size of both arrays is 2 then use this formula to get the median. Median = (max(a[0], b[0]) + min(a[1], b[1]))/2
  
Recursive Approach:
2. Calculate the medians for the input arrays 'a' and 'b' respectively. Say 'm1' is median of array 'a' and 'm2' is median of array 'b'.
3. If value of m1 is equal to m2 then we don't have to compute any further. Return m1 or m2.
4. If m1 > m2, then the median of the merged array must be present in one of the following two sub-arrays -
    a) Subarray starting from element m2(including m2) and ending at the last element of array 'b'. Therefore, we modify low index of array 'b' to the index of element m2.
    b) Subarray starting from the first element of array 'a' and ending at element m1(including m1). Therefore, we modify high index of array 'a' to the index of element m1.
5. If m2 > m1, then the median of the merged array must be present in one of the following two sub-arrays -
   a) Subarray starting from element m1(including m1) and ending at the last element of array 'a'. Therefore, we modify low index of array 'a' to the index of element m1.
   b) Subarray starting from the first element of array 'b' and ending at element m2(including m2). Therefore, we modify high index of array 'b' to the index of element m2.
6. With these modified low and high indices, we jump to step #2 until we hit base case(step #1).

Please check out the video for an illustrative explanation.


Algorithm Visualization




Code Snippet

			
package com.ideserve.nilesh.questions;

import java.util.ArrayList;

public class MedianOfTwoSortedArrays 
{
	private static final int ERROR_INVALID_INPUT = -1; // change value of this const as per your specific requirement
	
    public int max(int a, int b)
    {
        if (a > b) return a;
        return b;
    }
     
    public int min(int a, int b)
    {
        if (a < b) return a;
        return b;
    }
     
    private double findMedian(int[] array, int startIndex, int endIndex)
    {
    	int indexDiff = (endIndex - startIndex);
    	if (indexDiff % 2 == 0) // we are looking at odd number of elements
    	{
    		return array[startIndex + (indexDiff/2)];
    	}
    	else
    	{
    		return 1.0*(array[startIndex + (indexDiff/2)] + array[startIndex + (indexDiff/2) + 1])/2;
    	}
    }
    
    // a: 1,2,5,11,15  // b: 3 4 13 17 18
    public double findMedianSortedArrays(int[] a, int[] b, int startIndexA, int endIndexA, int startIndexB, int endIndexB)
    {
       
    	if ((endIndexA - startIndexA < 0) || ((endIndexB - startIndexB < 0)))
        {
    		System.out.println("Invalid Input.");
            return ERROR_INVALID_INPUT;
        }

        if ((endIndexA - startIndexA == 0) && ((endIndexB - startIndexB == 0)))
        {
            return (a[0] + b[0])/2;
        }
    	
        if ((endIndexA - startIndexA == 1) && ((endIndexB - startIndexB == 1)))
        {
            return (1.0*(max(a[startIndexA], b[startIndexB]) + min(a[endIndexA], b[endIndexB])))/2;
        }
         
        double m1 = findMedian(a, startIndexA, endIndexA);
        double m2 = findMedian(b, startIndexB, endIndexB);
         
        if (m2 == m1)
        {
            return m2;
        }
         
        // since m1 <= median <= m2 narrow down search by eliminating elements less than m1 and elements greater than m2  
        if (m1 < m2)
        {
        	if ((endIndexA - startIndexA) % 2 == 0) // we are looking at odd number of elements
        	{
        		startIndexA = startIndexA + (endIndexA - startIndexA) / 2;
        		endIndexB = startIndexB + (endIndexB - startIndexB) / 2;
        	}
        	else
        	{
        		startIndexA = startIndexA + (endIndexA - startIndexA) / 2;
        		endIndexB = startIndexB + (endIndexB - startIndexB) / 2 + 1;        		
        	}
        }
         
        // since m2 <= median <= m1 narrow down search by eliminating elements less than m2 and elements greater than m1
        else // m2 < m1
        {
        	if ((endIndexB - startIndexB) % 2 == 0) // we are looking at odd number of elements
        	{
        		startIndexB = startIndexB + (endIndexB - startIndexB) / 2;
        		endIndexA = startIndexA + (endIndexA - startIndexA) / 2;
        	}
        	else
        	{
        		startIndexB = startIndexB + (endIndexB - startIndexB) / 2;
        		endIndexA = startIndexA + (endIndexA - startIndexA) / 2 + 1;        		
        	}
        }
        return findMedianSortedArrays(a, b, startIndexA, endIndexA, startIndexB, endIndexB);
    }
     
    public static void main(String[] args)
    {
     
        MedianOfTwoSortedArrays solution = new MedianOfTwoSortedArrays();
       
	    System.out.println("Case 1: When arrays have odd number of elements in them.");
        int [] a = {1,2,3,4,5};
        int [] b = {6,7,8,9,10};
         
        System.out.println("Median: " + solution.findMedianSortedArrays(a, b, 0, a.length-1, 0, b.length-1));
		
		System.out.println("-----------------");
		
		System.out.println("Case 2: When arrays have even number of elements in them.");
		int[] c = {1,2,99, 100};
        int[] d = {4,5,101, 102};
         
        System.out.println("Median: " + solution.findMedianSortedArrays(c, d, 0, c.length-1, 0, d.length-1));
    }
}
		

Order of the Algorithm

Time Complexity is O(log(n))
Space Complexity is O(1)


Contribution

  • Sincere thanks from IDeserve community to Nilesh More for compiling current post.


    Nilesh More