the rank of median in the merged list of the two lists is (N1+N2)/2 so if it's rank in list A is i and it's rank in list B is j then i+j=(N1+N2)/2 (it's rank in the list that it does not belong is i when A[i]<median<A[i+1] )
we do an changed binary search as follows: pick the middle element of A it's index in A is i and since i+j=(N1+N2)/2 we can obtain j (it's rank in B if it's the median) then if B[j]<A[i]<B[j+1] , A[i] is the median (the same thing for B[j]) else whether A[i] is less than them or it's bigger than both of them if it's bigger than both of them the median is somewhere in the first half of A and the second half of B we can do the rest of search in there the opposite thing happens if it's less then B[j] and B[j+1] -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
