69. Square root of x

Method: binary search

• The square root of x must be less than or equal to x and greater than or equal to 1, so look in [1,x]
• The product of two ints can be out of bounds, so long is used.
• If x is a perfect square, then you can find mid*mid in the while exactly equal to x, such as the root of 16 is 4.
• If x is not a perfect square, you won’t find mid*mid exactly equal to x in while, such as finding the root of 8, because the actual root of 8 is 2.828. In this case, it is necessary to return an integer value that is closest to the root of x after exit. The value returned should be rounded down.

class Solution {
    public int mySqrt(int x) {
        // The square root of x must be less than or equal to x and greater than or equal to 1, so look in [1,x]
        long low = 1;
        long high = x;
        while (low <= high) {
            long mid = low + (high - low) / 2;
            long s = mid * mid;// Use long to prevent product overflow
            if (s == x) {
                return (int) mid;
            } else if (s > x) {
                high = mid - 1;
            } else {
                low = mid + 1; }}return (int) high;// Return the cause of high, draw a graph to analyze.}}Copy the code