69. Sqrt(x) (Easy) Facebook Bloomberg Apple

Implementint sqrt(int x).

Compute and return the square root ofx.

x is guaranteed to be a non-negative integer.

Example 1:

Input: 4
Output: 2

Example 2:

Input: 8
Output: 2
Explanation: The square root of 8 is 2.82842..., and since we want to return an integer, the decimal part will be truncated.

Solution 1: Binary Search O(logn); O(1) Template

    /**
     * Binary Search O(logn); O(1) Template
     * If x <= 1, return x.
     * Binary Search from 1 to x.
     * while start + 1 < end
     *   Calculate mid and compare mid with x / mid
     *   If mid = x / mid, square root found, return mid.
     *   If mid < x / mid, mid should be larger, start = mid.
     *   If mid > x / mid, mid should be smaller, end = mid.
     * return start. Here is a trick, because square root of integer should be rounded down.
     */
    public int mySqrt(int x) {
        if (x <= 1) {
            return x;
        }

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