There are two sorted arrays A and B 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)).

 

method 1, time complexity = O(max{m,n})

 

public class Solution {    public double findMedianSortedArrays(int A[], int B[]) {        double result = 0;		if(A.length != 0 || B.length != 0){			if(A.length == 0)				result = (B[(B.length - 1)/2] + B[B.length/2]) / 2.0;			if(B.length == 0)				result = (A[(A.length - 1)/2] + A[A.length/2]) / 2.0;			int length = A.length + B.length;			int[] total = new int[length];						int index1 = 0;			int index2 = 0;			for(int i = 0; i < length / 2 + 1; ++ i){				if(index1 < A.length && index2 < B.length){					if(A[index1] <= B[index2]){						total[i] = A[index1];						++index1;					}					else{						total[i] = B[index2];						++index2;					}				}				else if(index1 == A.length){					total[i] = B[index2];					++index2;				}				else{					total[i] = A[index1];					++index1;				}			}			result = (total[(length - 1)/2] + total[length /2]) / 2.0;		}		return result;    }}

　　

 

The O(log(m + n)) method

public class Solution {    public double findMedianSortedArrays(int A[], int B[]) {       int alen = A.length, blen = B.length;       if((alen + blen) % 2 != 0) //odd number of elements in total    	   return findHelper(A, B, (alen + blen) / 2 + 1, 0, alen - 1, 0, blen - 1);       else //even number of elements in total    	   return (findHelper(A, B, (alen + blen) / 2, 0, alen - 1, 0, blen - 1)     			 + findHelper(A, B, (alen + blen) / 2 + 1, 0, alen - 1, 0, blen - 1)) / 2.0;    }	private int findHelper(int A[], int B[], int k, int startA, int endA, int startB, int endB){		if(endA < startA)			return B[startB + k - 1];		if(endB < startB)			return A[startA + k - 1];		if(k == 1)			return Math.min(A[startA], B[startB]);				int lenA = endA - startA + 1;		int lenB = endB - startB + 1;				if(lenA > lenB)			return findHelper(B, A, k, startB, endB, startA, endA);		else {			int aMid = Math.min(k / 2, lenA);			int bMid = k - aMid;			if(A[startA + aMid - 1] < B[startB + bMid - 1])				return findHelper(A, B, k - aMid, startA + aMid, endA, startB, endB);			else if(A[startA + aMid - 1] > B[startB + bMid - 1])				return findHelper(A, B, k - bMid, startA, endA, startB + bMid, endB);			else //A[startA + aMid - 1] == B[startB + bMid - 1]				return A[startA + aMid - 1];		}    }}