> Big O tells us that a binary search is the most efficient search algorithm for an array (constraint - the array must be sorted), but in practice a linear sear

> Big O tells us that a binary search is the most efficient search algorithm for an array (constraint - the array must be sorted), but in practice a linear search with a sentinel value across an unsorted array will be faster if the array fits in cache. From a cache perspective, a binary search is actually the most pessimal case. If you want efficiency, look at b-trees optimized for memory hierarchies.