Leetcode 69. Sqrt(x)

Implement int sqrt(int x).

Compute and return the square root of x.

Analysis:

To get the sqrt of x, we can use binary search to have a mid value. Then check the value of mid * mid. If it equals to x, then that’s the sqrt. Otherwise, keep going and make the mid larger to less.

Note in the code, we should make the start, mid and end to be long to avoid the precision losing.

Time complexity: O(logn)

Space complexity: O(1)

Below is the code:

public class Solution {
    public int mySqrt(int x) {
        // O(logn) binary search
        
        // Corner case
        if (x == 0 || x == 1) {
            return x;
        }
        
        // Make them to be long 
        long start = 1;
        long end = x;
        
        while (start + 1 < end) {
            long mid = start + (end - start) / 2;
            
            if (mid * mid <= x) {
                start = mid;
            } else {
                end = mid;
            }
        }
        
        if (start * start <= x) {
            return (int) start;
        } else if (end * end <= x) {
            return (int) end;
        }
        
        return 0;
    }
}