Certainly you don't have to go beyond 2*sqrt(N) on the ++ side
The high side search would always have terminated there or earlier anyway as it stopped as soon as the difference between it and the root was greater than that between lo and root. Lo can't go below 1, so hi would never go above root*2-1. But skipping the hi search is much better.
Another optimisation possible if N is odd, is to step back by 2 each time.
Examine what is said, not who speaks.
Silence betokens consent.
Love the truth but pardon error.