algorithm - Number of integers in a list larger than a given integer possibly not in the list in log log time -

given unordered list of n nonnegative integers (with no guarantees distribution or repetition), want able given integer possibly not in list, , respond number of integers @ least large in list. have n^2 preprocessing time, , n*log(n) storage. possible?

my not-good-enough solution binary search (log n time, constant space).

storing map of possible queries in map take storage.

edit: partial solutions require assumption on inputs, such distribution or max size of integer, useful.

edit: known predecessor/successor problem. there's paper beame & fich in construct data structure stores n element sets of integers universe of size n in o(n) space , performs predecessor queries in o(min{(log log n) / (log log log n), sqrt(log n / (log log n))}) time.

http://homes.cs.washington.edu/~beame/papers/stocpred.pdf

edit - bounty: none of answers of morning i'm looking for. n not bounded. integers not under 32 bits. largest element may larger number of elements. assume no distribution on inputs. of existing answers, accepted coffin's bounty because covers relatively large subset of problems have distribution.

assuming elements reasonably evenly distributed (or @ least follow some distribution closely) obvious method sort data, use interpolating search instead of binary search.

an interpolating search typically has o(log log n) complexity.

oh, in case it's not obvious name, basic idea of interpolating search use interpolation guess @ approximate location of element you're searching for. if, example, you're dealing integers between 0 , 100,000, , need find, say, 21,000, can start @ location 21% of way array instead of starting halfway point. then, based on value find there, can use interpolation find better guess, , on.

that example linear interpolation, same basic idea applies other distributions well--you have use function fits (reasonably well) data's distribution.