Everyone is talking about this microoptimization on the math of the access but all I can think about is how the data structure you are building using this is pr

Everyone is talking about this microoptimization on the math of the access but all I can think about is how the data structure you are building using this is probably memory bandwidth limited and powers-of-two storage is almost definitely going to cause some kind of cache line aliasing, so maybe you should try something non-obvious like "division by 3" (after doing three key comparisons instead of one) and see if it makes your algorithm much much faster than messing around with a division by 2; there was even some good analysis of this effect a while back I can reference. https://pvk.ca/Blog/2012/07/30/binary-search-is-a-pathological-case-for-caches/ https://pvk.ca/Blog/2012/07/30/binary-search-is-a-pathologic...