Missing: conventional wisdom turned into lie

> If the array all fits in cache, binary search wins: both linear and
> binary search, at most, load the data into cache once. If the array is
> extremely large, binary search still wins despite the wasted reads of
> entire cache lines, because at some point N/log(N) exceeds the miss
> penalty.

This is exactly the conventional wisdom I think isn't true anymore for 
some realistic examples. You're missing the effect of the hardware 
prefetcher, which will, for some sizes, and esp. for cold caches lead to a 
performance increase for the linear search, as opposed to binary search, 
which looks like random access to the prefetcher, and therefore incurs the 
RAM->cache latency cost typically hidden by the prefetcher.