Beating Binary Search

This depend entirely on being able to do the interpolation on your keys. He computes:<p><pre><code> offset = (key - min) / (max - min) </code></pre> but not all data can have arithmetic done on it like that. What if the data in your array are, for example, names?<p>It's pretty trivial to beat binary search if your data are integers, or other keys on which you can do arithmetic. You can make the uniform distribution assumption, check it as you go, degrade to binary search if the assumption seems flawed, and then proceed from there.<p>However, if you're given an array of unknown objects, a comparison function, and no way to do arithmetic on your objects, you can't beat binary search.

I'm fascinated that so many of the commenters here seem to be focusing on the fact that the algorithm mentioned doesn't work in every case. My reaction was different -- I thought of a case where it would be less than ideal, and allowed it to inspire me to find an algorithm that worked better than naive binary search for that case, too.<p>In particular, I thought of the case of searching arrays of strings. If you are doing repeated searches against the same array, you can easily build a table breaking the array down into subarrays all sharing the same first character. (I'm assuming ASCII there!) Using that can quickly eliminate 5 or so comparisons that would be required with a naive binary search.<p>Okay, that's not brilliant, but might be useful in some circumstances. My bigger point is I thought this article was a very useful reminder that even a terrific general purpose algorithm like binary search can be beaten if you can apply specific domain knowledge to the search.

Caveat emptor: The article fails to mention that interpolation search's worst-case performance is O(n), considerably worse than binary search's O(log n).

I have thought about this years ago, simply because it is also kind of the way humans search in telephone books. (Advantage of being born in a time when telephone books where still in use). I think humans would also do repeated interpolation, as some letters would be "thicker" (more pages in the book) than others.<p>Bionics for the win...

You can beat pretty much any algorithm if you make convenient extra assumptions. In this case they have suitable data for the implication search (good for them!), but the title promises too much.<p>You can't beat binary search without new assumptions.

It works well only on uniformly distributed keys. Not everyone has pleasure to work with such data.

I do not know this language (Java?), but doesn't the line<p><pre><code> int offset = (int) (((size - 1) * ((long) key - min)) / (max - min)); </code></pre> compute (max - min) as an int (potentially overflowing), and then convert it to long, defeating the precautions obviously taken against this kind of event with the cast to long elsewhere?

Interesting article, but without actual numbers it's hard to tell whether the change made any difference in performance.