Day367: valid complete square

problem ： Effective complete square number

Given a positive integer num , Write a function , If num It's a complete square , Then return to true , Otherwise return to false .

Advanced ： Don't Use any built-in library functions , Such as sqrt .

source ： Power button （LeetCode）

Train of thought ： Brute force ergodic solution

For less than num Integer of from 1 To traverse the , Determine whether the square is equal to num, If equal to, return true, Otherwise return to false.

class Solution {
    
    public boolean isPerfectSquare(int num) {
    
        boolean result = false;
        if (num==1) result = true;
        for(int i=2; i < num/2+1; i++){
    
            if(i*i==num){
    
                result = true;
                break;
            }
        }
        return result;
    }
}

shortcoming ： When the integer is too large , Time limit exceeded .

Train of thought two ： Dichotomy

1. The root of a perfect square number x, Must be satisfied with $1\le x\le num$, We use this interval as the search interval .
2. left Start from the left side of the section ,right Start from the right side of the section , Calculate the median $mid=\frac{（left+right)}{2}$
3. Perfect square heel x Must satisfy one of the three relationships ,$mid==x,mid<x,mid>x$, So as left or right Update conditions for .
4. The dichotomy is compared to the violent solution , The time complexity is reduced to some extent .

class Solution {
    
    public boolean isPerfectSquare(int num) {
    
        int left = 0;
        int right = num;
        boolean result = false;
        while (left <= right){
    
            int mid = (left + right)/2;
            long mid_square = (long)mid*mid;
            if(mid_square < num){
    
                left = mid + 1;
            }else if(mid_square > num){
    
                right = mid - 1;
            }
            else{
    
                result = true;
                return result;
            }
        }
        return result;
    }
}

Train of thought three ： Newton method

Newton's method is an approximate method to solve the zero point of a function , The iterative idea is as follows .

For the function $f(x)$, Take any starting point $(x0,f(x0))$, Do the function at this point $f(x)$ The tangent of , Tangent and x Axis intersection point $x1$ Is the abscissa of the point to be updated next time , comparison $x0$ for ,$x1$ Closer to zero , After many iterations , It can be approximated as point $x1$ Approaching the zero of a function .

Ideas ：
In this case $f(x)=x^2-num$
Update formula $x_{i+1}=(x_i+num/x_i)/2$
The end condition ： We think that when the results of two adjacent iterations are similar , It can be considered close enough to zero .

Code ：

class Solution {
    
    public boolean isPerfectSquare(int num) {
    
        double x0 = num;
        double x1 = 0;
        while (true){
    
            x1 = (x0 + num/x0)/2;
            if (x0 - x1 < 1e-1)
                break;
            x0 = x1;
        }
        x1 = (int)x1; 
        return x1*x1 == num;
    }
}

Reference resources ： Try to answer the official questions