Since you know Long.MAX_VALUE in advance, you can hard-code it's square root. You can then perform a binary search between 1 and this pre-computed maximum.

It will remove the questionable "exponential search".

You will then also achieve a \$\mathcal{O}(\log \sqrt{N})\$ complexity (but using a well known algorithm)

Since you know Long.MAX_VALUE in advance, you can hard-code it's square root. You can then perform a binary search between 1 and this pre-computed maximum.

It will remove the questionable "exponential search".

You will then also achieve a \$\mathcal{O}(\log \sqrt{Long.MAX\_VALUE})\$ complexity, which is actually \$\mathcal{O}(1)\$ as observed by @Simon Forsberg. This means that the execution duration can be bounded by a constant time (this does not necessary means that this algorithm is the fastest).