Thank you for your incredible work! I have been reading Algorithms for Modern Hardware as part of my after-work study and I have found it invaluable—I reference it daily.
Thank you for your article. I had difficulty understanding the "Binary search implementation" section of the original article for various reasons, despite knowing what binary search is, being familiar with the 2k/2k+1 encoding (from binary heaps), and generally thinking I understood what you're trying to do. I wondered if was the only one struggling with this.
Among the difficulties:
"restore the index of the resulting element" - it's not clear what this means until after reading the remainder of the section (many times, in my case, due to other difficulties)
"We compare it against 4, 2, and 5..." - An error? You compared 'x' against 4, 2, and 3, or b[1], b[2], and b[5], but never against 5 - this would be to the right of 4 and a binary search would not visit it.
"..and so we just need to find the number of trailing ones in the binary notation and right-shift by exactly that amount." - You need to shift right that amount plus one. In your example for search(4), after the loop and prior to shifting k=11. In binary this is 1011, which has two trailing ones, but must be shifted right by 3 bits (not 2) to yield k=1 such that b[k] == 4.
"eytzinger: 4 2 5 1 6 3 7 8" - it took me surprisingly long to realize this was describing the permutation of values of a[] to indexes of b[] rather than listing the contents of b[] itself with the zero element elided (which coincidentally are the same for the first two elements, despite otherwise not making any sense). Perhaps brevity forces this sort of thing.
The presence of 8 in the example's array appears to be an error. At index 8 it would be the left child of 1, which it can't be. Letting n=7 and a={1,2,3,4,5,6,7} agrees with your example, whereas including 8 and setting n=8 rearranges things and forces the root to be 5 rather than 4.
Thanks for organizing this information into one place! It's super interesting and really relevant to high performance software. A lot of this material is scattered between conference talks, obscure forums, and hacks in closed-source software.
So, in your implementation, you always reduce the search range to n - n/2 to avoid branches. Why can it not be always n/2 - seeing as you've just examined and ruled out your middle element? i.e. seeing as how n/2 >= (n-1)-(n-1)/2 ?
This is a tricky part. The middle element is still part of the search range if we go "left" (≥). After we compare against it, the search range length becomes either floor(n/2) or ceil(n/2), in the latter case including the middle element (we will never compare against it again, but it still needs to be the first element of the search range).
To avoid additional checks and branching, we can just always make the next search range length ceil(n/2), effectively adding that middle element to the search range in case we go "right" (<).
I can’t wait for Part II :)