If your data follows a relatively uniform distribution, you can try out interpolation search: https://en.wikipedia.org/wiki/Interpolation_search