Antonio Gulli's coding playground

I guess I would try something similar to the QuickSort algo. Take a pivot, reorder the elements, if it's the k-th element in the reordered array then return that element, else go do the same step on the side which should contain the k-th elem. There might be a better approach.

complexity is log(N) I think

so not linked to the size of the interval? you could make it better

You can sort the elements in the [i, j] interval and take the k-th element in costant time. So the complexity is t log t where t=j-i.