Example 33
有效的完全平方数
题目概述：给定一个 正整数 num ，编写一个函数，如果 num 是一个完全平方数，则返回 true ，否则返回 false 。
进阶：不要使用任何内置的库函数，如sqrt 。
示例 1：
输入：num = 16
输出：true
示例 2：
输入：num = 14
输出：false
解题思路：使用二分查找。因为num 是正整数，所以若正整数x满足x*x=num，则x一定满足 1≤x≤num。于是可以将1和num作为二分查找搜索区间的初始边界。
因为在移动左侧边界left和右侧边界right时，新的搜索区间都不会包含被检查的下标mid，所以搜索区间的边界始终是没有检查过的。因此，当left=right时，仍需要检查mid=(left+right)/2。
解题步骤：
1. 定义变量left、right分别代表左、右指针指向的索引，其初值分别为0，num。
2. 定义while循环，当left小于等于right时，进入循环，继续考察，否则说明二分查找法首尾已经错开，且仍为找到目标值，即代表没有目标值，返回false。
3. 在while循环内部，定义变量mid代表当前起始点与终点的中间点。定义变量square代表中间点的平方（为避免平方时出现数据溢出，square应当定义为long型），以此与num作比较来判断目标值在mid的左/右侧。
4. 若square小于num，则说明目标值在mid的右侧，则将起始点更新为mid + 1，若square大于num，则说明目标值在mid的左侧，则将终点更新为mid - 1，否则说明square等于num，即找到目标点，返回true。
示例代码如下：
public class EffectiveCompleteSquare { /** * 给定一个 正整数 num ，编写一个函数，如果 num 是一个完全平方数，则返回 true ，否则返回 false 。 * 进阶：不要使用任何内置的库函数，如sqrt 。 * 示例 1： * 输入：num = 16 * 输出：true * 示例 2： * 输入：num = 14 * 输出：false * 来源：力扣（LeetCode） * 链接：https://leetcode.cn/problems/valid-perfect-square */ public static void main(String[] args) { EffectiveCompleteSquare ecs = new EffectiveCompleteSquare(); System.out.println(ecs.isPerfectSquare(2147483647)); // true } /** * 官方 * * @param num * @return */ public boolean isPerfectSquare(int num) { int left = 0, right = num; while (left <= right) { int mid = (right - left) / 2 + left; long square = (long) mid * mid; if (square < num) { left = mid + 1; } else if (square > num) { right = mid - 1; } else { return true; } } return false; } /** * 个人 * @param num * @return */ /*public boolean isPerfectSquare(int num) { int strat = 0; int end = num; long mid; while (strat <= end) { mid = (end + strat) / 2; if (mid * mid == num) return true; else if (mid * mid < num) strat = (int)mid + 1; else end = (int)mid - 1; } return false; }*/ }
