[mehrdadn]

> if your guess is completely wrong, will it still converge in no worse than O(log(N))?

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.)

[usmannk]

Is the trick quit and start doing a binary search?

[smallnamespace]

Ooh, or what about alternating interpolation and binary search steps?

Interpolation steps make quick progress if your distribution is correct.

[sritchie]

This sounds like Brent’s method for root finding! Also very similar is his method for Unitarians minimization. I ported this into Clojure recently from Python / FORTRAN... not quite literate programming but well documented if you want to give it a peek. https://github.com/littleredcomputer/sicmutils/blob/master/s...

[sillysaurusx]

That's actually quite clever. I like it.

I can't figure out the puzzle's answer. Hopefully they'll post the solution someday.

[mehrdadn]

Yup that was the answer :-) interleaving the two lets you get the best of both worlds at the cost of a constant-factor penalty. This is a pretty clever & general-purpose meta-algorithm that works for pretty much any problem where you have competing algorithms with different strengths.

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.

[whatshisface]

A strategy in use since the 1970s is to quit interpolation search when it starts picking values too close to the edge of the range, switching to binary search afterwards. That's a well known technique for finding the roots of polynomials.

>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. ;)