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 + bit): 
      ans += bit
   bit /= 2

Constant will be much smaller.