Assuming a random process X of n elements: X={x1,...,xn}.
For a given probability p, the corresponding quantile is determined through the quantile function Q defined as:
Q(p)={x|Pr(X<=x)=p}
What is the time complexity of finding the quantile of a given probability p?
Quickselect can use median of medians pivot selection to get O(n) worst-case runtime to select the kth order statistic. This appears to be more or less what you are after unless I am misinterpreting (you want the (n*p)'th smallest element).
You cannot possibly improve upon this in the general case: you must at least look at the whole array or else the element you didn't look at might be the answer you need.
Therefore, the Quickselect is theoretically optimal in the worst case. Note: this pivot selection strategy has bad constants and is not used in practice. In practice, using random pivot selection gives good expected performance but O(n^2) worst-case.