# Binary search solution in Python

• ``````class Solution(object):
def isPerfectSquare(self, num):
b, e = 1, (num >> 1) + 1
while b <= e:
mid = (b + e) >> 1
sq = mid * mid
if sq == num:
return True
if sq > num:
e = mid - 1
else:
b = mid + 1
return False``````

• This initialization can make it faster:

``````    b = 1 << max(num.bit_length() - 1, 0) / 2
e = 2 * b
``````

Testing a random 100000-bits number, this improved your time (on my PC) from 620 seconds to 207 seconds. (I was curious how it would do after I wrote this solution, which is faster for big numbers.)

• So your rationale is that `sqrt(n)` cannot be less than half the nearest power of two greater than `n`? Can you prove the validity of this assumption?

Also why not

``````b = (1 << max(num.bit_length() - 1, 0)) >> 1
e = b << 1
``````

It seems like you hate multiplications/divisions :-)

• Ts ts ts... shame on you for not knowing the Python operator precedences :-P
(`/` is stronger than `<<`)

But to handwavingly prove what I did say: For example for num=40 I get b=1<<(5/2)=4 and e=8. In fact I get b=4, e=8 for num from 16 to 63. And I get b=8, e=16 for num from 64 to 255. My b-formula always jumps to the next higher power of 2 exactly as soon as it can.

If you're referring to my complete lack of multiplications/divisions in my solution... actually I had and preferred `/ 2` and `2*i` somewhere and that totally wouldn't have hurt the point I was making, but I wanted to keep the title as it is and it would've been wrong and I didn't want to have to explain why it doesn't matter. (I actually did explain it and then hated it and deleted it.)

• Haha never had the patience to learn those! Now it's time!

• To be honest, I don't know them, either. But by now I know how to find them quickly :-)

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.