CODEWITHSUNDEEP
python-3.xbinary-search
Melissa Stewart
Melissa Stewart

Reputation: 3605

Binary search goes into infinite loop

I'm trying to find if a number is a perfect square. I have a simple binary search algorithm to do this, which ends up going into an infinite loop. I can't seem to find a way around this. Can someone help me with this.

def isPerfectSquare(self, num):
        """
        :type num: int
        :rtype: bool
        """
        if num < 1:
            return False
        start, end = 1, num
        while start <= end:
            mid = (end - start)//2
            if mid * mid == num:
                return True
            elif mid * mid < num:
                start = mid + 1
            else:
                end = mid
        return False

Upvotes: 1

Views: 75

Answers (1)

Melissa Stewart
Melissa Stewart

Reputation: 3605

I kind of found the problem, This is line of code which ends up with the wrong mid,

mid = (end - start)//2

Since we actually want a mid that is in the correct half, the code will be,

mid = start + (end - start) // 2 This fixes it.

Upvotes: 1

Related Questions