Author here. There is a newer and significantly expanded version of the article: <a href="https://en.algorithmica.org/hpc/data-structures/binary-search/" rel="nofollow">https://en.algorithmica.org/hpc/data-structures/binary-searc...</a>
There exists a 2022 CPPcon presentation covering efficient binary searching, which includes Eytzinger layouts [1].<p>[1] <a href="https://github.com/CppCon/CppCon2022/blob/main/Presentations/binary-search-cppcon.pdf">https://github.com/CppCon/CppCon2022/blob/main/Presentations...</a>
tl;dr:<p>1. Avoid branching by always reducing the search range from n to n-n/2 (never n/2).<p>2. Preprocess the input (a sorted array) to Eytzinger order: Middle element, then first and third quartile elements etc. Now, if your search checks an element at position k, it will next want to look at either position 2k or 2k+1.<p>3. Some minor tweaks like aligned storage and rounding up size to a power of 2.
A good alternative to binary search on modern hardware that should not be overlooked is indexed sequential search.<p><a href="https://www.geeksforgeeks.org/indexed-sequential-search/" rel="nofollow">https://www.geeksforgeeks.org/indexed-sequential-search/</a>
Eytzinger layouts are great, but they require more space if one is not allowed to touch the original sorted array. Then again, if you are allowed to use extra space, binary search can be implemented in worst-case constant time for integer arrays.