Measurements suggest that binary search is at least competitive with linear search and is often the winner, so it’s a reasonable default[1]. But naive binary s

Measurements suggest that binary search is at least competitive with linear search and is often the winner, so it’s a reasonable default[1]. But naive binary search can also be improved upon by dividing the searched space into 3 subranges instead of 2[2]. [1]: <https://www.pvk.ca/Blog/2012/07/03/binary-search-star-eliminates-star-branch-mispredictions/ https://www.pvk.ca/Blog/2012/07/03/binary-search-star-elimin...> [2]: <https://www.pvk.ca/Blog/2012/07/30/binary-search-is-a-pathological-case-for-caches/ https://www.pvk.ca/Blog/2012/07/30/binary-search-is-a-pathol...>