Find an unknown very large number Let's suppose there is a finite unknown number n (n can be very large, does not necessarily fit 64-bits; think of BigInteger in Java or long in Python) and a function cmp(x) that returns true if x &lt;= n.

Write a program to determine n in minimum number of calls to cmp.
Double our guess until we exceed n, then do binary search.  This is a reasonable approach until n could be very large, at which point you probably want to do more than doubling at each step.

b=1;
while (cmp(b)) b *= 2;
a = b/2;
while (a &lt; b-1) {  // invariant: a &lt;= n &lt; b
  m = (a+b)/2;
  if (cmp(m)) {
    a = m;
  } else { 
    b = m;
  }
}
return a;