> We can do this once, and then binary search a safety interval around that position. Alas, this only gets rid of the fast jumps at the beginning of the binary search, and for some reason, it ends up being slightly slower than binary search alone.

I don't get why you can't do this at each step.

I assume this doesn't improve perf much because you pretty quickly zoom in on a slice of hashes that are not evenly distributed. 37GB feels like a lot of hashes but it's pretty small compared to the space of all hashes, I suspect this approach would be more effective if we were searching over a much bigger chunk of data.