On Apr 30, 12:27 pm, Saurabh <saurabh...@gmail.com> wrote: > Two sorted sequences of size m and n are given. Write an efficient > algo to find k-th smallest element in the set of combined m+n > elements. Note that the best possible algorithm runs in O(log(max > (m,n))).
I will give a sketch of the main algorithm. Details can be easily filled in. Let me call the two lists as A and B. Without loss of generality, I will work out the solution only for non-trivial case (where the k-th smallest is smaller than some elements of both lists). For ease of discussion I also assume that both the lists have more than k elements. Key to the solution is to notice that any solution to this problem would have k/2+x smaller elements from one list and k/2-x from the second list. Since, k is known the goal of the algorithm is to determine x. This can be done by a 2-list binary search on A and B. The 2-list binary search can be done as follows: if A[k/2] > B[k/2], we will do the binary search on A between l_a (k/2 initially) and r_a (k initially) index and on B between l_b (0 initially) and r_b (k/2 initially) index. else ... 2. Recurse on the smaller lists with k/2 untill k/2 becomes 1 which would be trivially solvable base case. Proofs: Termination: at each recursive step k becomes half, hence at some point it would reduce to 1 and algo would terminate. Correctness: Every step eliminates k/2 smaller elements from the list. Hence, at termination it would have eliminated k=k/2+k/4+... elements. Runtime: The algorithm preseted would actually take O(log k). But in general the complexity would be min of O(log(max(A_len+B_len))) and O(log k). - Raghav Kumar Gautam --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
