有效的完全平方数（ LeetCode 367 ）
一、题目描述
给定一个 正整数 num ，编写一个函数，如果 num 是一个完全平方数，则返回 true ，否则返回 false 。
进阶：不要 使用任何内置的库函数，如 sqrt 。
示例 1：
输入：num = 16
输出：true
示例 2：
输入：num = 14
输出：false
提示：
1 <= num <= 2^31 - 1
二、题目解析
三、参考代码
1、Java 代码
// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 有效的完全平方数（ LeetCode 367 ）:https://leetcode-cn.com/problems/valid-perfect-square
class Solution {
public boolean isPerfectSquare(int num) {
// left 为当前区间最左侧的元素，可以获取到
int left = 0;
// right 为当前区间最右侧的元素，可以获取到
int right = num;
// 在区间 [left , right] 这个左闭右闭的区间里面去查找
// 查找什么呢？
// 查找是否存在一个数 a，使得 a * a = num
// 在 while 循环里面，left 不断的向右移动，而 right 不断的向左移动
// 当 [ left , right ] 这个区间不存在元素的时候，才跳出 while 循环，也就是当 left > right 时跳出循环
// 即当 left = right + 1 时，搜索区间没有元素了
// 由于 left 和 right 相遇的时候指向同一个元素，这个元素是存在于 [ left , right] 区间，这个区间就一个元素
// 所以此时 while 循环的判断可以使用等号
while (left <= right) {
// left + (right - left) / 2 和 (left + right) / 2 的结果相同
// 但是使用 left + (right - left) / 2 可以防止由于 left 、right 同时太大，导致相加的结果溢出的问题
// 比如数据 int 的最大值为 2,147,483,647
// 此时，left 为 2,147,483,640
// 此时，right 为 2,147,483,646
// 两者直接相加超过了 2,147,483,647，产生了溢出
int mid = left + (right - left) / 2;
// 判断中间元素的平方与 num 的大小
// 如果 mid * mid < num
// mid * mid 的数值有可能超过 int 类型的最大数
// 使用 long
long square = (long) mid * mid;
// 中间元素的平方小于了目标值 num
// 数组为 [ 0 , n ]
// 1、数组为有序数组，比如为递增数组
// 2、数组中不存在重复元素
// 由于该数组存在以上两个特点，所以 [ left , mid ] 这个区间中的所有元素的平方都小于目标值 num
// 因此，缩小查找区间为 [ mid + 1 , right]
if (square < num){
// 也就是说缩小之后的区间最左侧位置为 mid + 1
left = mid + 1;
// 中间元素的平方大于了目标值 num
// 数组为 [ 0 , n ]
// 1、数组为有序数组，比如为递增数组
// 2、数组中不存在重复元素
// 由于该数组存在以上两个特点，所以 [ mid , right ] 这个区间中的所有元素的平方都大于目标值 num
// 因此，缩小查找区间为 [ left , mid - 1]
}else if( square > num){
// 也就是说缩小之后的区间最右侧位置为 mid - 1
right = mid - 1 ;
// 中间元素的平方等于了目标值 num
}else if( square == num){
// 直接返回结果即可
return true;
}
}
// 查找完区间中的所有元素都没有找到，返回 false
return false;
}
}
2、C++ 代码
// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 有效的完全平方数（ LeetCode 367 ）:https://leetcode-cn.com/problems/valid-perfect-square
class Solution {
public:
bool isPerfectSquare(int num) {
// left 为当前区间最左侧的元素，可以获取到
int left = 0;
// right 为当前区间最右侧的元素，可以获取到
int right = num;
// 在区间 [left , right] 这个左闭右闭的区间里面去查找
// 查找什么呢？
// 查找是否存在一个数 a，使得 a * a = num
// 在 while 循环里面，left 不断的向右移动，而 right 不断的向左移动
// 当 [ left , right ] 这个区间不存在元素的时候，才跳出 while 循环，也就是当 left > right 时跳出循环
// 即当 left = right + 1 时，搜索区间没有元素了
// 由于 left 和 right 相遇的时候指向同一个元素，这个元素是存在于 [ left , right] 区间，这个区间就一个元素
// 所以此时 while 循环的判断可以使用等号
while (left <= right) {
// left + (right - left) / 2 和 (left + right) / 2 的结果相同
// 但是使用 left + (right - left) / 2 可以防止由于 left 、right 同时太大，导致相加的结果溢出的问题
// 比如数据 int 的最大值为 2,147,483,647
// 此时，left 为 2,147,483,640
// 此时，right 为 2,147,483,646
// 两者直接相加超过了 2,147,483,647，产生了溢出
int mid = left + (right - left) / 2;
// 判断中间元素的平方与 num 的大小
// 如果 mid * mid < num
// mid * mid 的数值有可能超过 int 类型的最大数
// 使用 long
long square = (long) mid * mid;
// 中间元素的平方小于了目标值 num
// 数组为 [ 0 , n ]
// 1、数组为有序数组，比如为递增数组
// 2、数组中不存在重复元素
// 由于该数组存在以上两个特点，所以 [ left , mid ] 这个区间中的所有元素的平方都小于目标值 num
// 因此，缩小查找区间为 [ mid + 1 , right]
if (square < num){
// 也就是说缩小之后的区间最左侧位置为 mid + 1
left = mid + 1;
// 中间元素的平方大于了目标值 num
// 数组为 [ 0 , n ]
// 1、数组为有序数组，比如为递增数组
// 2、数组中不存在重复元素
// 由于该数组存在以上两个特点，所以 [ mid , right ] 这个区间中的所有元素的平方都大于目标值 num
// 因此，缩小查找区间为 [ left , mid - 1]
}else if( square > num){
// 也就是说缩小之后的区间最右侧位置为 mid - 1
right = mid - 1 ;
// 中间元素的平方等于了目标值 num
}else if( square == num){
// 直接返回结果即可
return true;
}
}
// 查找完区间中的所有元素都没有找到，返回 false
return false;
}
};
3、Python 代码
# 登录 AlgoMooc 官网获取更多算法图解
# https://www.algomooc.com
# 作者：程序员吴师兄
# 代码有看不懂的地方一定要私聊咨询吴师兄呀
# 有效的完全平方数（ LeetCode 367 ）:https://leetcode-cn.com/problems/valid-perfect-square
class Solution:
def isPerfectSquare(self, num: int) -> bool:
# left 为当前区间最左侧的元素，可以获取到
left = 0
# right 为当前区间最右侧的元素，可以获取到
right = num
# 在区间 [left , right] 这个左闭右闭的区间里面去查找
# 查找什么呢？
# 查找是否存在一个数 a，使得 a * a = num
# 在 while 循环里面，left 不断的向右移动，而 right 不断的向左移动
# 当 [ left , right ] 这个区间不存在元素的时候，才跳出 while 循环，也就是当 left > right 时跳出循环
# 即当 left = right + 1 时，搜索区间没有元素了
# 由于 left 和 right 相遇的时候指向同一个元素，这个元素是存在于 [ left , right] 区间，这个区间就一个元素
# 所以此时 while 循环的判断可以使用等号
while left <= right :
# left + (right - left) / 2 和 (left + right) / 2 的结果相同
# 但是使用 left + (right - left) / 2 可以防止由于 left 、right 同时太大，导致相加的结果溢出的问题
# 比如数据 的最大值为 2,147,483,647
# 此时，left 为 2,147,483,640
# 此时，right 为 2,147,483,646
# 两者直接相加超过了 2,147,483,647，产生了溢出
mid = left + (right - left) // 2
# 判断中间元素的平方与 num 的大小
# 如果 mid * mid < num
# mid * mid 的数值有可能超过 类型的最大数
# 使用 long
square = mid * mid
# 中间元素的平方小于了目标值 num
# 数组为 [ 0 , n ]
# 1、数组为有序数组，比如为递增数组
# 2、数组中不存在重复元素
# 由于该数组存在以上两个特点，所以 [ left , mid ] 这个区间中的所有元素的平方都小于目标值 num
# 因此，缩小查找区间为 [ mid + 1 , right]
if square < num:
# 也就是说缩小之后的区间最左侧位置为 mid + 1
left = mid + 1
# 中间元素的平方大于了目标值 num
# 数组为 [ 0 , n ]
# 1、数组为有序数组，比如为递增数组
# 2、数组中不存在重复元素
# 由于该数组存在以上两个特点，所以 [ mid , right ] 这个区间中的所有元素的平方都大于目标值 num
# 因此，缩小查找区间为 [ left , mid - 1]
elif square > num :
# 也就是说缩小之后的区间最右侧位置为 mid - 1
right = mid - 1
# 中间元素的平方等于了目标值 num
elif square == num :
# 直接返回结果即可
return True
# 查找完区间中的所有元素都没有找到，返回 False
return False
