Find Median of Two Sorted Arrays

The question is to find the median of two sorted arrays of numbers. Write an algorithm running in O(log n) time.

The median of a list of numbers is the middle one when the list is sorted. When the list has even size, the median is the average of the two middle numbers. It is easy to find the median in one sorted array; just pick up the middle element (or the average of the two middle elements). For example, the median of the following array is 27:
{3, 9, 10, 27, 38, 43, 82}.

Given two sorted arrays, a simple way to find the median is to merge the two arrays and pick up the middle one. This approach requires scanning through array elements one by one, and it takes linear time O(n). The code is similar to the merge method in merge sort.

public static double median(int[] a, int[] b)
{
    int n = a.length + b.length;
    int i = 0, j = 0;
    int curr = 0, prev = 0;
    
    for (int k = 0; k <= n; k++)
    {
        if (i == a.length)
            curr = b[j++];
        else if (j == b.length)
            curr = a[i++];
        else if (a[i] < b[j])
            curr = a[i++];
        else // a[i] >= b[j]
            curr = b[j++];

        if (k == n/2)      // in the middle
            break;
        prev = curr;       // prev: (k-1)th
    }

    // odd number of elements
    if (n % 2 != 0)
        return curr;
    // even number of elements
    return (double)(prev + curr) / 2;
}

A better approach is to compare the medians of the two arrays, and this helps reducing the array size almost by half. The algorithm runs as follows:

• If one of the arrays is empty, return the median of the other one.
• Compare the medians of the two arrays.
• If the two medians are the same, return it.
• If the two arrays have size 1, return the average of the two medians.
• Recursion

static double median(int a[], int first, int last)
{
	if (first > last)
		return 0;
	int mid = (first + last) / 2;
	if ((first + last) % 2 == 0)
		return a[mid];
	else
		return (double) (a[mid] + a[mid+1]) / 2;
}

static double median(int a, int b, int c)
{
	if (a > b)
	{ int t = a; a = b; b = t; }

	return (c < a) ? a : ( (c < b) ? c : b ); 
}

static double median(int a, int b, int c, int d)
{
	if (a > b)
	{ int t = a; a = b; b = t; }
	
	if (c < a)
	{ int t = c; c = a; a = t; }
	else if (c > b)
	{ int t = c; c = b; b = t; }

	if (d < a)
	{ int t = d; d = a; a = t; }
	else if (d > b)
	{ int t = d; d = b; b = t; }

	return (c + d) / 2.0;
}

static double median(int a[], int ai, int aj, int b[], int bi, int bj)
{
	System.out.println(ai + ", " + aj + "      " + bi + ", " + bj );
	
	// make a.length <= b.length
	if (aj - ai > bj - bi)
		return median(b, bi, bj, a, ai, aj);
	
	if (aj - ai < 0)
		return median(b, bi, bj);

	if (ai == aj)
	{
		if (bi == bj)
			return (a[ai] + b[bi]) / 2.0;
		int bm = (bi + bj) / 2;
		if ((bj - bi) % 2 == 1)
			return median(a[ai], b[bm], b[bm + 1]);
		else
			return median(a[ai], b[bm - 1], b[bm], b[bm + 1]);
	}
	if (ai + 1 == aj)
	{
		int bm = (bi + bj) / 2;
		if (bj == bi + 1)
			return median(a[ai], a[aj], b[bi], b[bj]);
		if ((bj - bi) % 2 == 0)
			return median(b[bm], Math.min(a[ai], b[bm+1]), Math.max(a[aj], b[bm-1]));
		else
			return median(b[bm], b[bm+1], Math.min(a[ai], b[bm+2]), Math.max(a[aj], b[bm-1]));
	}
	

	int am = (ai + aj) / 2;
	int bm = (bi + bj) / 2;
	
	if (a[am] == b[bm])
		return a[am];
	
	int cut = am - ai;
	
	if (a[am] > b[bm])
		return median(a, ai, aj-cut, b, bi+cut, bj);

	return median(a, ai+cut, aj, b, bi, bj-cut);
}

Comments

comments