Skip to content

69 Sqrt(x) – Medium

Problem:

Implement int sqrt(int x).

Compute and return the square root of x.

Thoughts:

The most straight forward way it so iterate over all possible numbers, namely 1 to x/2+1.

But we could find it faster by using binary search. improving running time from O(x) to O(logx).

Plus, the condition to determine result is also critical, because we cannot say m*m == x is the checking condition.

Solutions:

public class Solution {
    public int mySqrt(int x) {
        int left = 1, right = x/2;
        while ( left <= right) {
            int mid = (left + right) /2;
            if (mid > x /mid) {
                right = mid - 1;
                continue;
            }
            if ((mid+1) <= x/(mid+1)) {
                left = mid + 1;
                continue;
            }
            return mid;
        }
        return x;
    }
}