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.
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.
ReplyDeletecomplexity is log(N) I think
so not linked to the size of the interval? you could make it better
ReplyDeleteYou 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.
ReplyDelete