If anyone's interested, there's a nice paper from 1976 (!) that goes into the details.
https://www.sciencedirect.com/science/article/pii/0020019076900715
For instance, you can do a binary search for the first phase, that is, not just double but initially you double, then quadruple, then times 8 and so forth. That would reduce the number of guesses in the first phase to around lg(lg(N)) instead of lg(N) while also not making the search interval for the second phase too big.