# Shar's Algorithm for Branchless Binary Search

*last updated: Oct 20, 2023*

https://probablydance.com/2023/04/27/beautiful-branchless-binary-search/

The author finds Shar's Algorithm from binary search, which is from TAOCP, and implements it in C++. Finds that it is sometimes faster than the standard library binary search, and does an excellent job benchmarking and explaining why it is or isn't in given scenarios.

This is theÂ second timeÂ that I came across an algorithm in Knuthâ€™s books that is brilliant and should be used more widely but somehow was forgotten. Maybe I should actually read the bookâ€¦ Itâ€™s just really hard to see which ideas are good and which ones arenâ€™t. For example immediately after sketching out Sharâ€™s algorithm, Knuth spends far more time going over a binary search based on the Fibonacci sequence. Itâ€™s faster if you canâ€™t quickly divide integers by 2, and instead only have addition and subtraction. So itâ€™s probably useless, but who knows? When reading Knuthâ€™s book, you have to assume that most algorithms are useless, and that the good things have been highlighted by someone already. Luckily for people like me, there seem to still be a few hidden gems.