http://sna-projects.com/blog/2010/06/beating-binary-search/

Instead of just picking the middle, guess the position where the target value appears, and compares the value in the position with the target. This obtains O(loglogN).