69 Sqrt(x)

Implementint sqrt(int x).

Compute and return the square root of x.

The Idea: The naive solution would be to return the first index in the for loop through x where $i*i=x$, since $\sqrt{x} = i*i$. With binary search, the idea is the same except that we begin our search within the bounds of [0, x], and eliminate the left or right half depending on whether the algorithm overestimated or underestimated the solution.

Below, when pow < x, we know this resulted in a underestimation so the next iteration will extend [mid+1, high].

Complexity: O(log(x)) time and O(log(x)) space

int mySqrt(int x)
{
    if (x == 0 || x == 1) return x;

    long long start = 1, end = x, mid, pow, ans;
    while (start <= end)
    {
        mid = (start + end) / 2;
        pow = mid*mid;

        if (pow == x) return mid;
        else if (pow < x) {
            start = mid + 1;
            ans = mid;
        }
        else end = mid - 1;

    }
    return ans;
}

int main()
{
    cout << mySqrt(2) << endl;
    cout << mySqrt(1) << endl;
    cout << mySqrt(2147483647) << endl;
}

Recursive Python Solution

import math


class Solution:
    def mySqrt(self, x):
        """
        :type x: int
        :rtype: int
        """

        def b_search(left, right):
            mid = int(left + (right - left) / 2)
            cur = math.pow(mid, 2)
            over = math.pow(mid + 1, 2) # when this over estimates but cur does not, then we found our solution
            if cur <= x < over:
                return int(mid)
            elif math.pow(mid, 2) > x:  # over estimation
                return b_search(left, mid - 1)
            else:
                return b_search(mid + 1, right)  # under estimation

        return b_search(0, x)