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
-~----------~----~----~----~------~----~------~--~---

Reply via email to