No, but there's a simple but powerful technique you can use to ensure this from the outside. See if you can figure it out. (If you don't, look up introsort.)
Interpolation steps make quick progress if your distribution is correct.
I can't figure out the puzzle's answer. Hopefully they'll post the solution someday.
Quitting and starting over as GGP mentioned is another option that also works for this problem, though it might not work as well for other problems where you can't put a nice bound on the number of steps.
FWIW there's also a very dumb (or smart I guess, depending on your point of view) solution, which is to just have 2 threads run simultaneously, and report the result of the first one. It might make sense for some problems. And in any case, this is basically equivalent to what you're doing on 1 CPU with the previous technique.
>This being said, I am not aware of interpolation search being actually used productively in software today. If you have a reference to such an artefact, please share!
This is also my response to that note in the article, interpolation search has been well-known in the numerical methods world since ancient times. ;)
I wonder what the worst case performance is -- if your guess is completely wrong, will it still converge in no worse than O(log(N))? Do you guess only once, at the beginning, or do you keep guessing where to go based on the distribution?
If you only guess once, at the beginning, then there's probably no risk. But if you keep trying to aim for the wrong target every iteration, I wouldn't be surprised if you get pathological behavior.
It would be kind of fun to try to calculate or simulate how bad it can get if you keep making incorrect guesses.