This is a beautiful way to express the algorithm. The magic that Don has omitted is that just as in normal binary search, you can hypthesize that A[i] is the k'th element meaning that A[1..i-1] <= k, which forces you to conclude the other k-i elements must be in the prefix of B, which is B[1..k-i]. This can be true only if B[k-i] <= A[i] <= B[k-i+1]. That is, A[i]'s value fits in the gap just after the prefix. If on the other hand A[i] is excessively small, B[1..k-i] > A[i], there are not enough small B elements to make k that are at most A[i], and we must consider larger i. On the other hand if A[i] is too big, A[i] > B[k-i+1], then there are too many small B elements to make exactly k. So we much consider smaller i values. Of course the search in array A can fail completely because the k'th element might be in B. When it fails, we can just reverse the roles of A and B and search again.
There are indexing details to work out for cases where k = i, |A|,|B| < k, etc. And you must be careful about duplicate values. But these are just icing. On Nov 15, 10:54 am, Don <dondod...@gmail.com> wrote: > Use a binary search to find a value i in the range 1..k such that > > A[i] >= B[k-i] and A[i] <= B[k-i+1], in which case A[i] is the result > > or > > A[i] <= B[k-i] and A[i+1] > B[k-i], in which case B[k-i] is the result > > Don > > On Nov 10, 10:07 am, shady <sinv...@gmail.com> wrote: > > > > > Given two sorted arrays, how to find the kth smallest element in the > > union of the arrays in a logarithmic time algorithm ? > > i have already formed a recursive solution, can anyone give the > > iterative approach, only pseudo-code :) -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
