This is a beautiful way to express the algorithm. The magic that Don
has omitted is that just as in normal binary search, you can
hypthesize that A[i] is the k'th element meaning that A[1..i-1] <= k,
which forces you to conclude the other k-i elements must be in the
prefix of B, which is B[1..k-i]
This is a beautiful way to express the algorithm. The magic that Don
has omitted is that just as in normal binary search, you can
hypthesize that A[i] is the k'th element meaning that A[1..i-1] <= k,
which forces you to conclude the other k-i elements must be in the
prefix of B, which is B[1..k-i]
Use a binary search to find a value i in the range 1..k such that
A[i] >= B[k-i] and A[i] <= B[k-i+1], in which case A[i] is the result
or
A[i] <= B[k-i] and A[i+1] > B[k-i], in which case B[k-i] is the result
Don
On Nov 10, 10:07 am, shady wrote:
> Given two sorted arrays, how to find the
Use a binary search to find a value i in the range 1..k such that
A[i] >= B[k-i] and A[i] <= B[k-i+1], in which case the median is A[i]
or
A[i] <= B[k-i] and A[i+1] > B[k-i], in which case B[k-i] is the
median.
Don
On Nov 10, 10:07 am, shady wrote:
> Given two sorted arrays, how to find th
that's a recursive solution, i have already solved it that way,
how to do it iteratively is the question .
On Sat, Nov 12, 2011 at 2:27 AM, Brijesh Upadhyay wrote:
> I guess this approach will work..
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorit
I guess this approach will work..
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/zeydVF1OqioJ.
To post to this group, send email to algogeeks@googlegroups.
FIND_PTH_SMALLEST(A, Astart, Aend, B, Bstart, Bend, p) // Check for
the special case when A and/or B have size one. if Astart ==
Aend AND Bstart == Bend return p == 1 ? min(A[1], B[1]) : max(A[1],
B[1])if Astart == Aend return max(min(A[1], B[Bend]),
B[Bend – 1])
what you didn't understand, logic or question ?
On Fri, Nov 11, 2011 at 10:05 PM, Ankuj Gupta wrote:
> I tried to understand the logic of it but could not :(
>
> On Nov 11, 11:17 am, shady wrote:
> > no, for eg.
> >
> > array1 = { 1, 2, 5, 6, 7, 7, 7, 23};
> > array2 = { 1, 2, 2, 4, 8, 9, 12 };
I tried to understand the logic of it but could not :(
On Nov 11, 11:17 am, shady wrote:
> no, for eg.
>
> array1 = { 1, 2, 5, 6, 7, 7, 7, 23};
> array2 = { 1, 2, 2, 4, 8, 9, 12 };
>
> then for
> k = 2, answer = 1
>
> k = 3, answer = 2
>
> k = 4, answer = 2,
>
> k = 6, answer = 4.
>
> anyway to d
no, for eg.
array1 = { 1, 2, 5, 6, 7, 7, 7, 23};
array2 = { 1, 2, 2, 4, 8, 9, 12 };
then for
k = 2, answer = 1
k = 3, answer = 2
k = 4, answer = 2,
k = 6, answer = 4.
anyway to do it iteratively in logarithmic time
On Fri, Nov 11, 2011 at 2:27 AM, sravanreddy001 wrote:
> Is it (k)th smalles
Is it (k)th smallest element (distict integers)
or the element at position k, when both are merged?
455566777
--> Is 3rd smallest element '1' or '4'
If four, I am not able to think of a log complexity. Can u post your
recursive
Step1: Find Median in those two sorted arrays.
Step2: if k < (length of array1 + length of array2) / 2 then search again
for median - k
else median + k
Will this work?
On Thu, Nov 10, 2011 at 9:45 PM, shady wrote:
> PS : there are duplicates also in both the arrays
>
> On Nov 10, 9:07 pm, shady
PS : there are duplicates also in both the arrays
On Nov 10, 9:07 pm, shady wrote:
> Given two sorted arrays, how to find the kth smallest element in the
> union of the arrays in a logarithmic time algorithm ?
> i have already formed a recursive solution, can anyone give the
> iterative approach,
Just do a little changes on your given function, that may help you
understand it:
We denote the transformed function as heap_compare_new:
int heap_compare_new(priority_queue *q, int i, int count, int x)
{
if ((count >= k) || (i > q->n) return(k-count);
/* change */
if (q->q[i] < x) {
count++;
14 matches
Mail list logo
