To select kth item among n.
Sample r = n^a (a is < 1) items at random, sort them. Make each sample item count for n^(1-a) original items. Select the k/n^(1-a)th item in the sample. kth original item is within sqrt(r) sample items to the left and right of that item with high probability. If the interval is on the left, start with comparison on the left bound. If the interval is on the left, start with comparison with the right bound. Compute the items in that interval in < 1.5 comparisons. If interval is too big to sort, restart the algorithm. It will be small with high probability anyway so just sort it and return the (k-l)th item in this set, where l is the number of elements to the left of the left bound.
Might also work with n^a = n/log n.
make-github-pseudonymous-again
commented
4 years ago
To select kth item among n. Sample r = n^a (a is < 1) items at random, sort them. Make each sample item count for n^(1-a) original items. Select the k/n^(1-a)th item in the sample. kth original item is within sqrt(r) sample items to the left and right of that item with high probability. If the interval is on the left, start with comparison on the left bound. If the interval is on the left, start with comparison with the right bound. Compute the items in that interval in < 1.5 comparisons. If interval is too big to sort, restart the algorithm. It will be small with high probability anyway so just sort it and return the (k-l)th item in this set, where l is the number of elements to the left of the left bound. Might also work with n^a = n/log n.