For an input array of values I[], create an array A = [ 0 ... n ] so that n = len(I). Sort the indices in A based on their corresponding value in I. Now A is t

For an input array of values I[], create an array A = [ 0 ... n ] so that n = len(I). Sort the indices in A based on their corresponding value in I. Now A is the mapping, A[n] is the index in I of the n+1:th largest value, and you can binary search in the same way, by comparing I[A[i]]. This is strictly more space efficient than a hash table. You're not going to win any awards for being cache efficient, but then again, when the competition is a damn hash table it's not too bad ;P