JS代码题16

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

说明：不要使用任何内置的库函数，如 sqrt。
示例 1：

输入：16
输出：True

示例 2：

输入：14
输出：False

1. 什么是完全平方数

完全平方指用一个整数乘以自己例如1×1，2×2，3×3等，依此类推。若一个数能表示成某个整数的平方的形式，则称这个数为完全平方数。

0也是完全平方数

2. 解答

2.1 暴力破解（循环查找）

var isPerfectSquare = function(num) {
    var i = 0
    while(i<=num){
        if(i*i===num){
            return true
        }else{
            i++
        }
    }
    return false
};

该方法因为要查找0到目标数值的所有数，耗时较长

2.2 二分查找

var isPerfectSquare = function(num) {
    var min = 0
    var max = num
    var mid
    while(min<=max){
        mid = Math.round((min+max)/2) //mid只能是整数
        if(mid*mid === num){
            return true
        }else if(mid*mid>num){
            max = mid - 1 //注意减一和加一
        }else{
            min = mid + 1
        }
    }
    return false
};

mid为目标数值
在找到目标数值之前，每一轮查找都把查找范围一分为二，缩短了查找时间