0367. 有效的完全平方数 #

标签：数学、二分查找
难度：简单

题目大意 #

给定一个正整数 num，判断 num 是不是完全平方数。要求：不能使用内置的库函数，如 sqrt。

解题思路 #

若 num 是完全平方数，则 num = x * x，x 为整数。问题就变为了对于正整数 num，是否能找到一个整数 x，使得 x * x = num。

x 可以通过二分查找得到。

代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


class Solution:
    def isPerfectSquare(self, num: int) -> bool:
        left = 0
        right = num
        while left < right:
            mid = left + (right - left) // 2
            if mid * mid > num:
                right = mid - 1
            elif mid * mid < num:
                left = mid + 1
            else:
                left = mid
                break
        return left * left == num