[koverstreet]

Yeah, I get that. What I was getting at is that binary searches are terrible in general are _terrible_ as soon as you're not hitting cache anymore - and for any problem worth optimizing that's what happens, if nothing else because your data set doesn't fit in l2 anymore.

Worrying about stuff not being cached because of associativity is pointless when the last 5-10 levels aren't going to be in cache anyways because they don't fit; those last 5-10 cache misses are going to _utterly dominate_ your search time.

IOW, even if associativity isn't a problem at all, binary searches suck w.r.t. caches - I'm not at all saying they're wrong, just that it's not terribly relevant - if performance matters you need to be doing something other than a binary search.