Finding the (probable) maximum of a large set of integers *without* iterating over all of the values

As in the title, I am trying to find the largest (aka least upper bound) of a (very large) set of integers. Importantly, I do not have direct access to the full list of integers, but I do have a function $f(n)$ which returns true/false if $n$ is in the set. The function $f(n)$ is expensive and I would like to minimize the number of calls I must make to it.

The integers might or might not be consecutive, or have large gaps between them (i.e. might be sparse or dense). There is no prior-known upper bound on the largest integer in the set, which can go off to infinity in theory.

Is there a well-trodden algorithm for doing this? My inkling is to do some kind of random sample to determine the density, and then try to find the upper bound within some certainty. I'm not sure how to bound my initial sample properly then though, or which distribution I might assume the integers have based on that sample.

Thanks.

• Can you formulate a concrete problem? Jun 10 '17 at 13:59
• This is impossible without more information. If the largest number you've tested is $k$, you have no information about whether $k+1$ is in the set. You can't give a certainty without knowing an a-priori distribution. Jun 10 '17 at 19:21
• It's of course not possible without more restrictions, but it does remind me of the German Tank Problem. Nov 19 '21 at 19:14

But let's say that p (n) = $1 / n^2$. The probability that there is any element n ≥ N is about 1/N. So 10 is an upper bound with probability 90%, 100 is an upper bound with probability 99% and so on. On the other hand, your checks will likely show that 1 is an element and find no others. p (n) could be any of a gazillion of possible probabilities.