On Apr 30, 12:27 pm, Saurabh 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. Det
Sent from my Verizon Wireless BlackBerry
-Original Message-
From: m...@vzw.blackberry.net
Date: Thu, 30 Apr 2009 23:30:37
To: ;
Subject: Re: [algogeeks] Re: find k-th smallest element in the set of combined
m+n elements
Combine means "combine". P=NP. The combined set
So then indeed we have a polynomial time algorithm.
Sent from my Verizon Wireless BlackBerry
-Original Message-
From: "Tanna, Nisarg"
Date: Thu, 30 Apr 2009 08:58:11
To:
Subject: [algogeeks] find k-th smallest element in the set of combined m+n
elements
Hi Saurabh,
Here are the
Yes, please.
Sent from my Verizon Wireless BlackBerry
-Original Message-
From: Sinan BAKIR
Date: Thu, 30 Apr 2009 18:40:22
To:
Subject: [algogeeks] Re: find k-th smallest element in the set of combined m+n
elements
what do you mean by combine? will the combined set going to be
This is very old problem, and the solution is well known.
2009/5/1 Dave
>
> 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
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 ne
what do you mean by combine? will the combined set going to be sorted as
well ?
2009/4/30 Saurabh
>
> 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
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 bin
