For those that haven't heard of it, there's something called interpolation search, which can beat binary search.
Here is a write up I did about it which compares it vs binary search with different distributions of data.
It also shows a hybrid approach that interleaves binary search steps and interpolation search steps, and seems to do quite well in the general case, compared to either search type individually.
https://blog.demofox.org/2019/03/22/linear-fit-search/