Leetcode (69) -- square root of X

Leetcode（69）——x The square root of

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 .

Tips ：

• $0$ <= x <= $2^{31-1}$

Answer key

Method 1 ： Brute force

Ideas

​​   because $x$ The value rounded down by the arithmetic square root of must be $[0,x]$ in , So directly and violently from $0$ Traversing $x$, Until you find the first square greater than $x$ Value , It subtracts $1$ Is the value we want to find .

Code implementation

My own ：

class Solution {
    
public:
    int mySqrt(int x) {
    
        long n;
        for(n = 0; n*n <= x; n++);
        return n-1;
    }
};

Complexity analysis

Time complexity ：$O(x)$, The worst case is from $0$ Find the $x$ Just found it
Spatial complexity ：$O(1)$.

Method 2 ： Two points search

Ideas

​​   because $x$ The integer part of the square root $\text{ans}$ yes Satisfy $k^2\le x$ Maximum $k$ value , So we can do something about $k$ Do a binary search , To get the answer .

​​   The lower bound of binary search is $0$, The upper bound can be roughly set to $x$. In each step of binary search , We just need to compare the intermediate elements $\text{mid}$ The sum of the squares of $x$ The size of the relationship , The range of the upper and lower bounds is adjusted by comparing the results . Because all our operations are integer operations , There will be no error , So when you get the final answer $\text{ans}$ after , There is no need to try again $\text{ans}+1$ 了 .

Code implementation

Leetcode Official explanation ：

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

my ：

class Solution {
    
public:
    int mySqrt(int x) {
    
        long min = 0, max = x, mid;
        while(min <= max){
    
            mid = (min + max)/2;
            if(mid*mid < x){
    
                if((mid+1)*(mid+1) > x) break;
                else min = mid+1;
            }else if(mid*mid > x) max = mid-1;
            else break;
        }
        return mid;
    }
};

Complexity analysis

Time complexity ：$O(logx)$, That is, the number of times needed for binary search .
Spatial complexity ：$O(1)$.

Method 3 ： Newton's iteration

Ideas

​​   Newton's iteration It is a method that can be used to quickly solve the zero point of a function .

For narrative purposes , We use it $C$ Represents the integer for which the square root is to be found . obviously ,$C$ The square root of is a function
$$y=f(x)=x^2-C$$

Zero point of .

​​   The essence of Newton's iterative method With the help of Taylor series , Approaching zero point quickly from initial value . Let's take one $x_0$ As an initial value , In each iteration , We find the point on the graph of the function $(x_i,f(x_i))$, Make a slope across the point as the derivative of the point $f^{\prime }(x_i)$ The straight line of , The point of intersection with the horizontal axis is marked as $x_{i+1}$.$x_{i+1}$ Compare with $x_i$ It's closer to zero . After many iterations , We can get a point of intersection very close to zero . The figure below shows the results from $x_0$ Start iterating twice , obtain $x_1$ and $x_2$ The process of .

Algorithm

We choose $x_0=C$ As an initial value .

In each iteration , We pass through the current intersection $x_i$, Find the point on the function image $(x_i,x_i^2-C)$, Make a slope of $f^{\prime }(x_i)=2x_i$ The straight line of , The equation of a straight line is ：
$$\begin{array}{rl}{y}_l& =2x_i(x-x_i)+x_i^2-C\\ & =2x_{i}x-(x_i^2+C)\end{array}$$

The intersection with the horizontal axis is the equation $2x_{i}x-(x_i^2+C)=0$ Solution , This is the new iteration result $x_{i+1}$：
$$x_{i+1}=\frac{1}{2}\left(x_i+\frac{C}{x_i}\right)$$

It's going on $k$ After iterations ,$x_k$ And the real zero $\sqrt{C}$ Close enough to , That's the answer .

details

• Why choose $x_0=C$ As an initial value ？

​​   because $y=x^2-C$ There are two zeros $-\sqrt{C}$ and $\sqrt{C}$. If we take a smaller initial value , It may iterate to $-\sqrt{C}$ This zero point , What we hope to find is $\sqrt{C}$ This zero point . So choose $x_0=C$ As an initial value , Every iteration has $x_{i+1}<x_i$, zero $\sqrt{C}$ On its left , So we must iterate to this zero .

• When does the iteration end ？

​​   After each iteration , We will all be further away from zero , So when the intersection of two adjacent iterations is very close , We can conclude , The result at this time is enough for us to get the answer . Generally speaking , We can judge whether the difference between the results of two adjacent iterations is less than a minimal non negative number $ϵ$, among $ϵ$ Generally, you can take $10^{-6}$ or $10^{-7}$.

• How to get the final answer through the approximate zero obtained by iteration ？

​​   because $y=f(x)$ stay $[\sqrt{C},+\infty ]$ Is a convex function （convex function） And constant greater than or equal to zero , So as long as we choose the initial value $x_0$ Greater than or equal to $\sqrt{C}$, The result of each iteration $x_i$ Will always be greater than or equal to $\sqrt{C}$. So long as $ϵ$ The choice is small enough , Final result $x_k$ It will only be slightly greater than the real zero $\sqrt{C}$. Given in the title 32 Bit integer range , The following will not happen ：

The real zero is $n-1/2ϵ$, among $n$ Is a positive integer , And the result of our iteration is $n+1/2ϵ$. After reserving the integer part of the result, we get $n$, But the correct result is $n-1$.

Code implementation

Leetcode Official explanation ：

class Solution {
    
public:
    int mySqrt(int x) {
    
        long ans = x;
        while(ans * ans > x)
            ans = (ans + x/ans)/2;
        return ans;
    }
};

Complexity analysis

Time complexity ：$O(\log x)$, This method is quadratic convergent , Faster than binary search .
Spatial complexity ：$O(1)$.

Method four ： Pocket calculator algorithm

Ideas

​​  「 Pocket calculator algorithm 」 Is an exponential function $\exp$ Logarithmic function $\ln$ Instead of the square root function . We can use finite mathematical functions , Get the result we want to calculate .

We will $\sqrt{x}$ Written as a power $x^{1/2}$, Then use the natural logarithm $e$ Change the bottom , You can get
$$\sqrt{x}=x^{1/2}=(e^{\ln x}{)}^{1/2}=e^{\frac{1}{2}\ln x}$$

So we can get $\sqrt{x}$ The value of the .

​​   Be careful ： Because the computer cannot store the exact value of floating point numbers （ For the storage method of floating point numbers, please refer to IEEE 754, No more details here ）, The parameters and return values of exponential function and logarithmic function are floating-point numbers , Therefore, there will be errors in the operation process . For example, when x = 2147395600x=2147395600 when ,$e^{\frac{1}{2}\ln x}$ Calculation results and correct values 4634046340 Difference between $10^{-11}$, In this way, when taking the integer part of the result , You'll get 4633946339 The wrong result .

​​   So in the integer part of the result $\text{ans}$ after , We should find out $\text{ans}$ And $\text{ans}+1$ Which one of them is the real answer .

Code implementation

Leetcode Official explanation ：

class Solution {
    
public:
    int mySqrt(int x) {
    
        if (x == 0) {
    
            return 0;
        }
        int ans = exp(0.5 * log(x));
        return ((long long)(ans + 1) * (ans + 1) <= x ? ans + 1 : ans);
    }
};

Complexity analysis

Time complexity ：$O(1)$, Because of the built-in exp Function and log Functions are generally fast , Here we regard its complexity as $O(1)$.
Spatial complexity ：$O(1)$.