I checked the plot against an old school project where I investigated binary search, and I got similar numbers for the "standard" binary search (std::lower_bound in my project): For N=1000,10000,100000 it took 713,925,1264 us (compare to the author's 750,960,1256 us).
In my project I didn't test "quaternary search", but instead the winner was the Eytzinger layout that others have discussed, with 570,808,1044 us (compare to author's quaternary search: 557,764,1009 us).
It would be interesting to try a 4-way Eytzinger layout.
In my project I didn't test "quaternary search", but instead the winner was the Eytzinger layout that others have discussed, with 570,808,1044 us (compare to author's quaternary search: 557,764,1009 us).
It would be interesting to try a 4-way Eytzinger layout.
My project report, if anyone's interested: https://dl.strova.dk/ksb-manuel-rav-algorithm-engineering-20...
EDIT: I reuploaded the linked PDF since the first one I uploaded was missing the source code.