Question

Formatted question description: https://leetcode.ca/all/69.html

Implement int sqrt(int x).

Compute and return the square root of x.

Algorithm

Binary search method to find square root.

Code

Java

public class Sqrt_x {

    public class Solution {

        // @memorize: divide and conquer, in fact it's a binary search. compare with pow() question
        public int mySqrt(int x) {
            // @note: x < 0, then return Imaginary number?
            // proof: sqrt(x) <= x/2, then, x <= x^2/4, then, x^2 - 4x >= 0, then x>=4

            if (x < 0) {
                return -1;
            }

            if (x == 0 || x == 1) {
                return x;
            }

            int low = 1; // lowBoundary
            int up = x; // upBoundary
            int mid = -1;
            while (low <= up) {
                mid = low + (up - low) / 2;

                // if (mid * mid == x) // @note: overflow
                if (mid <= x / mid && (mid + 1) > x / (mid + 1)) { // eg: 2^2 <=5, 3^2 > 5
                    return mid;
                } else if (mid < x / mid) {
                    low = mid + 1;
                } else {
                    up = mid - 1;
                }
            }

            return mid;
        }
    }

}

All Problems

All Solutions