Use a binary search. Assume that you have arrays a[m] and b[n] sorted in ascending order. If a[i] is the kth smallest element, then b[k-i-2] must be smaller than a[i], and b[k-i-1] must be larger (assuming arrays are zero-based). After using a binary search to find the value of i to meet this condition with k = (m+n)/2, you have to determine if a[i] or b[k-i-1] is the final answer. The complexity is O(log m).
Dave On Sunday, January 5, 2014 5:34:12 AM UTC-6, Sanjay Rajpal wrote: > Hi guys, > > Please help me in finding median of two sorted arrays of length m and n in > minimum possible time. > > > Thanks, > Sanjay > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected].
