[数据结构与算法]5--数组--【367】有效的完全平方数

题目

给定一个 正整数 num ，编写一个函数，如果 num 是一个完全平方数，则返回 true ，否则返回 false 。
进阶：不要 使用任何内置的库函数，如 sqrt 。
示例 1：
输入：num = 16
输出：true
示例 2：
输入：num = 14
输出：false

分析

解一：牛顿迭代法
解二：sqrt函数法，但是题目中不准用
解三：二分法

代码

解一：

var isPerfectSquare = function(num) {
    //牛顿迭代法
    let n = num
    while(n*n>num){
        n = Math.floor((n+num/n)/2)
    }
    return n*n === num
};

解二：

var isPerfectSquare = function(num) {
				if(Math.floor(Math.sqrt(num)) == Math.sqrt(num)){
					return true
				}
				return false
};

解三：

var isPerfectSquare = function(num) {
    //二分法
    let left = 0, right=num
    while(left<right){
        // let mid = Math.floor((left+right)/2)
        let mid = left + right + 1 >> 1  //?
        // let mid = left + Math.floor((right-left)/2)
        if(mid*mid===num) return true
        if(mid*mid<num){
            left = mid
        }else{
            right = mid-1
        }
    }
    return false
};

注意

利用二分法求解在更新mid值得这一步中，也就是我打问号的地方，需要注意的是，可以用Math.floor((left+right)/2)来更新，也可以用left+Math.floor((right-left)/2)来更新，但是最好的方法就是用（left+right+1）>>1来更新，因为运算的速度会很快。