I was asked a question in an exam

You are given an array A[1..n] of length n with each cell containing a ⟨height,weight⟩ pair. All height values are distinct, and so are all weight values. The array is sorted in increasing order of the height values. Your task is to design a recursive divide-and-conquer algorithm that given an integer k ∈ [1, n], finds the entry with the kth smallest weight value. You are allowed to use only O (1) extra space in every level of recursion. Though your algorithm is permitted to reorder the entries of A if required, it must restore the original order of the entries before termination. Your algorithm must run in Θ (n) time.

Does such an algorithm exist? I can use the Deterministic Select Algorithm to find the kth smallest weight value. But this would require some shuffles to find pivots where any element before pivots location is lesser and any element above pivots location is greater.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.