Implement randomized Quickselect without k-shift bug
Overview
This question evaluates understanding of randomized Quickselect and selection algorithms, including in-place partition semantics for the k-th largest element, careful index and k-update reasoning to prevent k-shift/off-by-one bugs, handling duplicates and adversarial pivots, and analysis of expected versus worst-case time and auxiliary space.
Implement randomized Quickselect to return the k-th largest element (1-based k, 1 ≤ k ≤ n) from an unsorted integer array. Use an in-place partition that places elements greater than the pivot to the left and less than the pivot to the right, returning the pivot’s final index p. Let rank = p - left + 1 (the number of elements ≥ pivot in the current subarray). If k == rank, return A[p]; if k < rank, recurse on [left..p-1]; otherwise recurse on [p+1..right] with k' = k - rank. Prove that this k-update rule prevents negative positions and off-by-one errors. Handle duplicates, very small arrays, and adversarial inputs by choosing a random pivot each iteration. Analyze expected time O(n) and worst-case time O(n^2), and specify auxiliary space. Finally, show how to adapt the same routine to find the k-th smallest and explain the difference from Quicksort.