There is new method of binary search which may be exist but I didn't see it.

Instead of using left and right, we can simply add new bit to our answer if it is possible:

while bit > 0:
   if check(ans + plus): 
      ans += plus
   plus /= 2

Constant will be much smaller.