Binary search is log time but otherwise pretty awful. If you don’t specifically need a sorted array, use something like a B-tree instead.

> I'd also want to try interpolation search for this

Years ago, when ORC unwinding tables were being implemented for the Linux kernel, the main performance bottleneck was binary search to turn a virtual address into an unwind record. I suggested adding a little array to reduce the range to be binary searched, and this was a huge speed up.

The same trick could work for floats as in the article: use an order-preserving float to int mapping and find the range of mapped integers that actually exist in the data set. Divide it equally into, say, a few thousand buckets. For each bucket, record the first index in the actual table that corresponds to that bucket. Then, to look up an actual entry, query two adjacent table entries to find the subrange that needs to be binary searched and search that.

The benefit will depend on the distribution of the table. In the best case it will eliminate the log factor entirely and make each lookup take a small constant number of queries.

I imagine a similar trick could be used with B-trees, but it would be more complex.