Does the QuickSelect algorithm work with duplicate values?
If I haven an Array
int[] array = {9, 8, 7, 6, 6, 6, 5, 0, 1, 2, 3, 4, 5, 5, 7, 200};
Will it be able to get the kth smallest element even though there are duplicates?
Yes, it works. By the end of every iteration you have all elements less than current pivot stored to the left of the pivot.
Let's consider case when all elements are the same. In this case every iteration ends up putting pivot element to the left of the array. And the next iteration will continue with one element shorter array. So we need k iterations to find k-th smallest element.