In your case it would be better to use interpolation search[1][2] instead of binary search.

[1] http://en.wikipedia.org/wiki/Interpolation_search [2] http://sna-projects.com/blog/2010/06/beating-binary-search/