This is very old problem, and the solution is well known. 2009/5/1 Dave <[email protected]>
> > This algorithm doesn't work. > Try A = 2, 6, 10, 14, 18, 22, 26 > and B = 4, 12, 20, 28, 36, 44, 52 > with k = 6. > You find x = A[6] = 22 (assuming 1-based arrays) or 26 (assuming 0- > based arrays) > Search B for 21 or 25, but don't find it. > So return 22 or 26. But the 6th smallest value is 14. > > You also need to take care of the case where k > m so that you can't > reference A[k]. > > I have an idea for a solution. I hope to post it tomorrow. > > Dave > > On Apr 30, 10:36 am, Nick <[email protected]> wrote: > > Here are the steps: > > > > Assume arrays A[n] and B[m] > > > > - x = A[k] > > - Look for value (x-1) in array B. Binary search will take O(logm) > > time. > > - If no such value is present then return x > > - If such a value is present at index l, then return (A[k-l] > B[l]? A > > [k-l] : B[l]) > > > > As you can see there is only 1 binary search performed. Rest is the > > constant time operation. > > > > On Apr 30, 3:27 am, Saurabh <[email protected]> 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))).- Hide quoted text - > > > > - Show quoted text - > > > --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
