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]) if Bstart == Bend return max(min(A[Aend],
B[1]),
A[Aend – 1])
// Get the correct indices to work with. i = floor((p+1)/
2) j = ceil((p+1)/2) if i > Aend j += i –
Aend i = Aend if j > Bend i += j –
Bend j = Bend
// Check the Sandwich Conditions. if A[i – 1] =< B[j] AND B[j]
=< A[i] return B[j] if B[j – 1] =< A[i] AND A[i] =< B[j] return
A[i]
// Recursively call the function and throw away parts of the array
you don’t want. if A[i] > B[j] return FIND_PTH_SMALLEST(A, Astart, i,
B, j, Bend, p – j – 1) else return FIND_PTH_SMALLEST(A, i, Aend, B,
Bstart, j, p – i – 1)
On Nov 10, 11:07 am, shady <[email protected]> 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, only pseudo-code :)
--
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?hl=en.
