leetcode 69. Square root of X

difficulty ： Simple
The frequency of ：77
subject ： Give you a nonnegative integer x , Calculate and return x Of Arithmetical square root .

Because the return type is an integer , Results are retained only Integral part , The decimal part will be Give up .

Be careful ： No built-in exponential functions and operators are allowed , for example pow(x, 0.5) perhaps x ** 0.5 .

Their thinking ： Two points search

• Binary search is the open root value
• Because it is possible that the open radical value is a decimal , That is, there is no equality . So you can't judge to wait first mid*mid==x
• Take out the decimal point , That is to say, the square of the calculated value is always less than the true open radical value , So please mid*mid Can only <=x

Code ：

class Solution {
    
    public int mySqrt(int x) {
    
        int l=0,r=x,res=-1;
        while(l<=r){
    
            int mid=(l+r)/2;
            // here mid*mid No parentheses 
            // Because only integers , That is to say, the value we want to get must be less than the true open radical 
            // Only when it is smaller than the true open root , Is the correct value , If it exceeds the true open radical value , That is wrong 
            if((long)mid*mid<=x){
    
                // The middle value is less than X, That explains. X The open radical of is on the right  
                res=mid;
                l=mid+1;
            }else{
    
                // It can also be on the left 
                r=mid-1;
            }
        }
        return res;
    }
}