力扣刷题367——有效的完全平方数（69的相似题）

题目：

给你一个正整数 num 。如果 num 是一个完全平方数，则返回 true ，否则返回 false 。

完全平方数 是一个可以写成某个整数的平方的整数。换句话说，它可以写成某个整数和自身的乘积。

不能使用任何内置的库函数，如 sqrt 。

作答情况（Python3版本）

class Solution:def isPerfectSquare(self, num: int) -> bool:left, right = 1, numif num==0:return Falsewhile left <= right:mid = left + (right - left) // 2square = mid * midif square == num:return Trueelif square < num:left = mid + 1else:right = mid - 1return False

解题思路

• 需要在整数范围内寻找满足 k² = num 的 k，暴力法是容易想到的方法，但是对于这个题目来说，与69不同，如果穷举k,会陷入无限循环，假如num不是完全平方数，那么将会永远找不到k，会陷入无限循环。
• k 的取值范围是 [1, num]（因为 1² = 1，而 num² 显然大于 num，除非 num=1）并且k² 的值随着 k 的增加而单调递增。这种有序性和单调性是二分查找的典型适用场景
• 二分查找的核心思想是通过比较中间值来缩小搜索范围，故我们可以初始化搜索范围为 [left=1, right=num]，后面照搬二分查找的经典逻辑思路。