69. square root of X

Title Description ：

Give you a nonnegative integer x , Calculate and return  x  The arithmetic square root of .

Because the return type is an integer , The result is only the integral part , The decimal part will be removed .

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

Topic analysis ：

For this problem, we need to understand a mathematical law ： A positive number x The square root of is >= x / 2, With this rule, we can think of dichotomy to choose to do this problem .

1. Dichotomy

int mySqrt(int x){
   int left=1;
   int right=x/2+1;       // Here itself can be x/2 But because of 0 Consideration of this factor , therefore right+1
   while(left<=right){
       int mid = left+((right-left)>>1);// This is equivalent to  mid = （right+left）/2 , It is written here to avoid overflow 
       if(mid>x/mid){
           right=mid-1;
       }
       else if(mid<x/mid){
           left=mid+1;
       }
       else{
           return mid;  // If the conditions are met, return 
       }
   }
   return right; // The last thing to return is the value rounded to zero , Therefore return right
}

2. Newton's iteration

Ideas

Newton iterative method is a method that can be used to quickly solve the zero of function .

f(y) = y^2 - C

take C Switch to Introduction value , be y Is the value .

The code is as follows ：

int mySqrt(int x){
  
  if(x==0){      // A special case 
      return 0;
  }
    double c=x;
    double x0=x;
    while(1){
        double x1 = (x0+c/x0)*0.5;
        if(fabs(x0-x1)<1e-7){       // The distance between the two is less than e*10^-7 Power exit 
            break;
        }
        x0=x1;
    }
    return (int)x0;      // Returns the rounded value 
}