力扣刷題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

解題思路

• 需要在整數范圍內尋找滿足 k2 = num 的 k，暴力法是容易想到的方法，但是對于這個題目來說，與69不同，如果窮舉k,會陷入無限循環，假如num不是完全平方數，那么將會永遠找不到k，會陷入無限循環。
• k 的取值范圍是 [1, num]（因為 12 = 1，而 num2 顯然大于 num，除非 num=1）并且k2 的值隨著 k 的增加而單調遞增。這種有序性和單調性是二分查找的典型適用場景
• 二分查找的核心思想是通過比較中間值來縮小搜索范圍，故我們可以初始化搜索范圍為 [left=1, right=num]，后面照搬二分查找的經典邏輯思路。