[binary search] 69 Square root of X

Binary search basis

One 、 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 .

Example 1：

Input ：x = 4
Output ：2
Example 2：

Input ：x = 8
Output ：2
explain ：8 The arithmetic square root of is 2.82842…, Because the return type is an integer , The decimal part will be removed .

Two 、 Answer key

• First, the initial interval is defined as the left closed and right closed interval , Search between edges, so l<=r, Because when the left is closed and the right is closed , It is found that only one number remains within the boundary , for example [5,5] reasonable .
• Then you just need to select the values in the interval in the order of binary search to substitute them into the problem solving .
  （1） Smaller than the target value , Take the right half interval
  （2） It is larger than the target value , Take left half interval
  （3） Equal to the target value , Return intermediate value
  （4） Until you find the whole range , There is no equal value , namely l>r, Round down according to the intention of the question , Returns a small value r

3、 ... and 、 Code

class Solution {
    
public:
    int mySqrt(int x) {
    
       if(x==0) return 0;
       int l = 1;
       int r = x;
       int mid ,sqrt;
       while(l<=r){
    
           mid = ((l+r)/ 2;
           sqrt = x / mid;
           if(sqrt > mid) l = mid + 1;
           else if(sqrt < mid) r = mid - 1;
           else return mid;
       }
       return r;
    }
};