LeetCode_二分搜索_简单_367.有效的完全平方数

1.题目

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

进阶：不要使用任何内置的库函数，如 sqrt 。

示例 1：
输入：num = 16
输出：true

示例 2：
输入：num = 14
输出：false

提示：
1 <= num <= 2³¹ - 1

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/valid-perfect-square

2.思路

（1）使用 Math.sqrt()
如果使用 Java 中内置的库函数 Math.sqrt() 的话，那么直接比较 (int)Math.sqrt((double) num) * (int)Math.sqrt((double) num) 与 num 是否相等即可。如果相等，则说明 num 是一个完全平方数；否则不则是。

（2）二分搜索
如果不使用任何内置的库函数的话，通过二分搜索的方法也可以进行判断。即我们需要在有序序列 [1 … num / 2] 中查找平方值为 num 的整数 mid，如果存在返回 true，否则返回 false。在使用二分搜索框架的过程中，本题有以下两点需要注意：
① 之所以搜索的右边界为 num / 2 而不是 num，主要目的在于缩小搜索区间，因为当正整数 num > 1 时，sqrt(num) ≤ num / 2；
② 在判断 mid 是否是 num 的算术平方根时，不能使用 mid * mid == num 进行判断，因为当 mid 大于 sqrt(Integer.MAX_VALUE) 时，前者会出现整数溢出的情况，从而影响判断。所以我们可以通过 mid == num / (double)mid 来进行判断。

3.代码实现（Java）

//思路1————使用 Math.sqrt()
class Solution {
    
    public boolean isPerfectSquare(int num) {
    
        return (int)Math.sqrt((double) num) * (int)Math.sqrt((double) num) == num;
    }
}

//思路2————二分搜索
class Solution {
    
    public static boolean isPerfectSquare(int num) {
    
        if (num == 1) {
    
            return true;
        }
        int left = 0;
        int right = num / 2;
        while (left <= right) {
    
            int mid = left + (right - left) / 2;
            // 如果使用 mid * mid 与 num 进行判断，前者可能会出现整数溢出的情况
            if (mid == num / (double)mid) {
    
                return true;
            } else if (mid < num / (double)mid) {
    
                left = mid + 1;
            } else {
    
                right = mid - 1;
            }
        }
        return false;
    }
}