You can beat the binary search

https://www.p99conf.io/session/40x-faster-binary-search/

How's that compare to this?

Another interesting case to analyze would be where the array is 2d and values increase to the right and upwards.