Cache-oblivious optimizations of binary search

Branch-free search

Prefetch optimization

Sqrt-optimization

VEB layout

Look-Up Tables

And some combinations Best: branch-free prefetch sqrt optimization - sqrt + prefetch on first step, branch-free + prefetch on second step, best match when all the data fits into cache-line.