Median of Two Sorted Arrays

Problem:

There are two sorted arrays nums1 and nums2 of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

Example
Given A=[1,2,3,4,5,6] and B=[2,3,4,5], the median is 3.5.

Given A=[1,2,3] and B=[4,5], the median is 3.

Challenge
The overall run time complexity should be O(log (m+n)).
Leetcode link
Lintcode link

My Solution:

This is a classic problem, which can be viewed as another form: “Given two sorted array, how to find the k-th largest number among both arrays?”.

The k in this problem is “total length / 2” for odd number. If the total length is even, we need to find “total length / 2” and “total length / 2 + 1” number, and then get the average value.

The most intuitive solution is to merge them and find the k-th number, which takes O(M + N);

There is a better solution. Assume both amount of elements in A and B are greater than k / 2. If we compare the (k / 2)-th value in A (A[k / 2 - 1]) and the (k / 2)-th value in B (B[k / 2 - 1]), we have three possilbe cases:

  • If A[k / 2 - 1] == B[k / 2 - 1], we can say the value is the k-th value we want.
  • If A[k / 2 - 1] < B[k / 2 - 1], it means integer from A[0] to A[k / 2 - 1] should be smaller than the k-th value, so we can drop these values.
  • If A[k / 2 - 1] > B[k / 2 - 1], it means integer from B[0] to B[k / 2 - 1] should be smaller than the k-th value, so we can drop these values.

To drop the values in A and B, we can use two pointers to point to the start index of A and B respectively.
We can build a recursion whose stop points are:

  • If the start index pointer of A or B exceed the length, return B[BStart + k - 1] or A[AStart + k - 1];
  • If k == 1, return the minimum of A[AStart] or B[BStart]
  • If A[AStart + k / 2 -1] == B[BStart + k / 2 -1], return the value.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/*************************************************************************
> File Name: MedianOfTwoSortedArray.java
> Author: Yao Zhang
> Mail: psyyz10@163.com
> Created Time: Tue 10 Nov 22:01:06 2015
************************************************************************/


public class MedianOfTwoSortedArray{
public double findMedianSortedArrays(int[] A, int[] B) {
int len = A.length + B.length;
if (len % 2 != 0)
return findKth(A,0,B,0,len / 2 + 1);
else
return (findKth(A,0,B,0,len / 2) + findKth(A,0,B,0,len / 2 + 1)) / 2.0;
}

public static int findKth(int[] A, int AStart,
int[] B, int BStart, int k)
{

if (AStart >= A.length)
return B[BStart + k - 1] ;
if (BStart >= B.length)
return A[AStart + k - 1] ;
if (k == 1)
return Math.min(A[AStart],B[BStart]);

int va = AStart + k / 2 <= A.length ?
A[AStart + k / 2 -1] : Integer.MAX_VALUE;
int vb = BStart + k / 2 <= B.length ?
B[BStart + k / 2 -1] : Integer.MAX_VALUE;

if (va < vb)
return findKth(A, AStart + k / 2, B, BStart, k - k / 2);
else if (va > vb)
return findKth(A, AStart, B, BStart + k / 2, k - k / 2);
else
return va;
}
}