leetcode.367 (有效的完全平方数) （牛顿迭代法）

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

牛顿迭代法+二分查找法

方法一：类似二分查找方法
代码如下：
从temp= num/2 开始，如果temp^2 > num 就让 temp/2;
如果 temp^2 < num , 就让temp+1;

注意修改一下num的类型值，把int改成long long，这样不会有数据超出Int范围的问题。

class Solution {
public:
    bool isPerfectSquare(long long num) {
        if(num==0||num==1)return true;
        long long temp=num/2;
        while(temp){
            if(temp*temp==num)return true;
            else if(temp*temp<num){              
                temp++;
                if(temp*temp==num)return true;
                else if(temp*temp>num)break;
            }
                
            else temp=temp/2;
        }
        return false;
    }
};

方法二：牛顿迭代法：
牛顿迭代法原理：

将问题转换成找出 f(x)=x^2-num=0 的解的问题。
假设初始迭代值为Xk 则在(Xk, f(Xk)) 这个点的切线与x轴交点为 Xk+1

因此，可以通过不停地迭代，找到最靠近零点的点。

最后，如果迭代的点的平方不大于num值，则停止迭代。
此时所得的预测值得平方<=num。
最后再判断预测值是不是有效的平方根即可

代码如下：

class Solution {
public:
    bool isPerfectSquare(long long num) {
        if(num==0||num==1)return true;
        long long temp=num/2;
        while(temp*temp>num){
            temp=(temp+num/temp)/2;
        }
        return temp*temp==num;
    }
};