Adding “educated guesses” to binary search does seem pretty obvious. Kinda surprised I haven’t heard of it before. But the author is probably right, lg lg n is probably not too much better than lg n…