“This is the third day of my participation in the Gwen Challenge in November. Check out the details: The last Gwen Challenge in 2021.”

preface

Sqrt(x) is shown as follows:

Given a non-negative integer x, compute and return the arithmetic square root of x.

Since the return type is an integer, only the integer part of the result is retained, and the decimal part is omitted.

Note: It is not allowed to use any built-in exponential functions and operators, such as POw (x, 0.5) or x ** 0.5.

Example 1:

Input: x = 4 Output: 2Copy the code

Example 2:

Input: x = 8 Output: 2 Explanation: The arithmetic square root of 8 is 2.82842... Because the return type is an integer, the decimal part will be omitted.Copy the code

A, thinking

The integer part of the arithmetical square root of x. Since we only need the integer part of the arithmetic square root, we just need to find the maximum value I can take when I * I <= x

To quickly find the arithmetic square root of x, we can use dichotomy to find this result. The general steps are as follows:

  1. Handles special values: whenx < 2Direct returnxCan be
  2. The left margin is set to0, the right boundary is set tox. As long as the median squared is less than or equal toxI’m going to put the left boundaryleft = mid+1, other cases will be right borderright = mid -1
  3. End the binary loop and return the result

For example

Take x = 26 as an example

  1. left = 0.right = 26. At this timemid = 13, easy to knowmid * mid > x, so it will beright = mid - 1 = 12
  2. left = 0.right = 12. At this timemid = 6, easy to knowmid * mid > x, so it will beright = mid - 1 = 5
  3. left = 0.right = 5. At this timemid = 2, easy to knowmid * mid < x, so it will beleft = mid + 1 = 3And assign the resultret = 2
  4. left = 3.right = 5. At this timemid = 4, easy to knowmid * mid < x, so it will beleft = mid + 1 = 5And assign the resultret = 4
  5. left = 5.right = 5. At this timemid = 5, easy to knowmid * mid < x, so it will beleft = mid + 1 = 6And assign the resultret = 5
  6. left = 6.right = 5At this time,left > right, end the loop
  7. Returns the result5Can be

Second, the implementation

The implementation code

The implementation code is consistent with the idea

    /** * dichotomy */
    public int mySqrt(int x) {
        // Special circumstances
        if (x==0 || x==1)
            return x;
        int left = 0, right = x;
        int ret = 0;
        while (left <= right) {
            int mid = (left + right) / 2;
            if ((long) mid * mid <= x) {
                ret = mid;
                left = mid + 1;
            } else {
                right = mid - 1; }}return ret;
    }
Copy the code

The test code

    public static void main(String[] args) {
        new Number69().mySqrt(26);
    }
Copy the code

The results of

Third, summary

Thank you to see the end, very honored to help you ~♥

If you think my writing is good, you might as well give me a thumbs-up! If you have any questions, please see the comments section