This wouldn't go into a standard library since it's distribution dependent, but you might be interested to note a non-trivial (nor game changing) improvement to

This wouldn't go into a standard library since it's distribution dependent, but you might be interested to note a non-trivial (nor game changing) improvement to leveldb query time even with all the other work that it's doing besides search. Other examples would include things like pandas joins which use primitives like searching for lower bounds and partition points. I agree because for datasets that fit into memory, the scope for improvement is pretty limited. From a billion elements to 128 billion, that's only around 23% (37/30) more comparisons for binary search, and keeping that constant at the expense of more linear search isn't necessarily all that interesting for cheap comparisons. LogN grows so slowly that log-logN is frequently not that practically interesting.