You can beat the binary search
Summary
Daniel Lemire introduces the SIMD Quad algorithm, a hybrid search method for 16-bit sorted arrays that combines a quaternary interpolation search over 16-element blocks with SIMD comparisons. The approach, benchmarked against std::find and std::binary_search on Intel and Apple platforms, generally outperforms binary search, especially on cold caches, and demonstrates how leveraging memory-level and data parallelism can beat classic algorithms.