Binary search solution in Python


  • 3
    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

  • 0

    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.)


  • 0

    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 :-)


  • 0

    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.)


  • 0

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


  • 0

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


Log in to reply
 

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