SquareRoot.java

public class SquareRoot {
    static int naive(int x) {
        if (x == 0 || x == 1) { return x; }
        for (int i = 2; i < x; i++) {
            long temp = i * i;
            if (temp > x) {
                return i - 1;
            }
        }
        return -1;
    }

    static int binarySearch(int x) {
        if (x == 0 || x == 1) { return x; }
        long low = 1; long high = x;
        long result = 0;
        while (low <= high) {
            long mid = (low + high) / 2;
            long temp = mid * mid;
            if (temp == x) {
                return (int)mid;
            } else if (temp <= x) {
                low = mid + 1;
                result = mid;
            } else {
                high = mid - 1;
            }
        }
        return (int)result;
    }

    static int newtonRaphson(int x) {
        long i = x;
        long temp = i * i;
        while (temp > x) {
            i = (i + x / i) / 2;
            temp = i * i;
        }
        return (int)i;
    }

    public static void main(String[] args) {
        System.out.println(naive(11));
        System.out.println(binarySearch(11));
        System.out.println(newtonRaphson(11));
        System.out.println(newtonRaphson(2147395599));
        System.out.println(binarySearch(2147395599));
        System.out.println(naive(2147395599));
    }
}