# The Problem:

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)).

# Notes:

- The median is the middle element in a sorted array if length is odd, the average of the two middle elements if length is even.
- Solution is required to be of O(log(m+n)), and two arrays are sorted, so here comes binary search. We convert the problem of finding middle element to be finding the k-th element, and then the binary search is not always divide with the same length.
- In each recursion, discard part of A and B, with start and end index passed to next step, and update the k. If A[ida] < B[idb], means the part in A before ida are all of index less than k in merged array, and the part in B after idb are all of index greater than k in merged array, discard those two parts.
- Mistakes I made:
- when calculating the k related index in B, be careful of index-length conversion, should -1 here. Also should use the index count taken in A, not the index, so add astart to ida after B has calculated index.
- End condition need be thorough to include if either one has length zero.

# Java Solution

public class Solution { public double findMedianSortedArrays(int A[], int B[]) { int lena = A.length; int lenb = B.length; if((lena + lenb)%2==0){// return (mid1+mid2)/2 double mid1 = (double)getkth((lena+lenb)/2, A, 0, lena-1, B, 0, lenb-1); double mid2 = (double)getkth((lena+lenb)/2-1, A,0, lena-1, B, 0, lenb-1); return (mid1+mid2)/2; } else{ return (double)getkth((lena+lenb)/2, A,0, lena-1, B, 0,lenb-1); } } private int getkth(int k, int A[], int astart, int aend, int B[], int bstart, int bend){ int lena = aend-astart+1; int lenb = bend-bstart+1; if(lena==0) return B[bstart+k]; if(lenb==0) return A[astart+k]; if(k==0) return Math.min(A[astart], B[bstart]); int ida = k*lena/(lena+lenb); int idb = bstart + k-ida -1; //--!! important of -1, and here ida is used as count, not index ida = astart+ida; // --!! important to convert to index if(A[ida] <= B[idb]){// discard the part after idb in B and part before ida in A k = k-(ida-astart+1); astart = ida+1; bend = idb; } else{// discard the part after ida in A and part before idb in B k = k-(idb-bstart+1); bstart = idb+1; aend = ida; } return getkth(k, A, astart, aend, B, bstart, bend); } }

Advertisements