I wonder if we're simply in violent agreement - it certainly seems to me that you just aren't getting my point, and while much of what you say is true, it just doesn't seem relevant to me.
Yes, Interpolation Search has better average complexity in those circumstances when it works. However, for almost all cases of Binary Search that I use, Interpolation Search won't work, and isn't applicable. I was trying to make that point.
If your vector is sorted then it's reasonable to assume you have a comparison function between the objects in your vector. Binary Search then requires nothing more than this absolute minimum - just a comparison function. In this case Interpolation Search doesn't work at all.
As Colin pointed out above, it actually gets worse for our author. In cases where the volumes are sufficient to make much of a difference, you are almost certainly going to want to take caching and access speeds into account. Now you need to move out of the realm of Binary or Interpolation Search and into other data structures anyway.
Yes, Interpolation Search is cool and works in a small niche of cases. But mostly, it's irrelevant.
And that's my summary. Cool, but mostly either inapplicable or irrelevant.
I think you're overstating how often you're only going have a sorted vector of unknown type and an opaque comparison function, and understating how often you'll know your types and be able to make a reasonable guess at their distribution.
You're also ignoring how much simpler it is to roll a quick interpolation search than throw together a B+-Tree, to the point where it may make sense as something to try when you've got an hour to try to speed up some process just enough to get you through another week of growing load while you're rewriting your app to do it right.
Yes, Interpolation Search has better average complexity in those circumstances when it works. However, for almost all cases of Binary Search that I use, Interpolation Search won't work, and isn't applicable. I was trying to make that point.
If your vector is sorted then it's reasonable to assume you have a comparison function between the objects in your vector. Binary Search then requires nothing more than this absolute minimum - just a comparison function. In this case Interpolation Search doesn't work at all.
As Colin pointed out above, it actually gets worse for our author. In cases where the volumes are sufficient to make much of a difference, you are almost certainly going to want to take caching and access speeds into account. Now you need to move out of the realm of Binary or Interpolation Search and into other data structures anyway.
Yes, Interpolation Search is cool and works in a small niche of cases. But mostly, it's irrelevant.
And that's my summary. Cool, but mostly either inapplicable or irrelevant.