Sqrt(x)

Implement int sqrt(int x).

Compute and return the square root of x.

Solution

public class Solution {
    public int mySqrt(int x) {
              if (x == 0 || x == 1) {
            return x;
        }

        int start = 1;
        int end = x;
        while (start <= end) {
            int middle = start + (end - start) / 2;
            if (x / middle == middle ) return middle;
            else if (x / middle < middle) end = middle - 1;
            else start = middle + 1;
        }

        return end;
    }
}