Then subtract the subset. =P Sent from my Verizon Wireless BlackBerry -----Original Message----- From: Dave <dave_and_da...@juno.com>
Date: Thu, 30 Apr 2009 21:05:56 To: Algorithm Geeks<algogeeks@googlegroups.com> Subject: [algogeeks] Re: find k-th smallest element in the set of combined m+n elements 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 <nisargta...@gmail.com> 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 <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))).- 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 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 -~----------~----~----~----~------~----~------~--~---
