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

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. But, yes, I'll agree with your summary.