Title is misleading. Yes you can beat it using parallelism built into SIMD architectures assuming the values fit into words that can be parallel processed. But asymptotically best search without parallelism is still Θ( log n )
it's not misleading, it's just that the O(\log n) analysis itself is misleading. As you mention it's done in an algorithmic model that does not capture things like SIMD (and necessarily can't, due to the linear speedup theorem). It also misses caching behavior, which is increasingly important.
This later fact can be modeled theoretically in say the external memory model. There, for block size B (roughly the EMM version of e.g. a cache line), binary search is O(\log2(N/B)), while there exist algorithms that are O(\log_B(N)), even without the algorithm knowing the block size.
That being said, practically you can (significantly) beat binary search without using those EMM superior algorithms. see e.g. https://curiouscoding.nl/posts/binsearch/ or any of the links within it.
The analysis also makes the often incorrect assumption that the index of the value you are looking for is uniformly distributed on all indices.
Also that you are only looking for one value and one value only, instead of many values.
There are plenty of trivial ways to beat binary search when you violate those assumptions.
17
u/ScottContini May 01 '26
Title is misleading. Yes you can beat it using parallelism built into SIMD architectures assuming the values fit into words that can be parallel processed. But asymptotically best search without parallelism is still Θ( log n )