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 <sinv...@gmail.com> 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 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?hl=en.