Sqrt(x)

Implement int sqrt(int x).

Compute and return the square root of x.

Example

sqrt(3) = 1

sqrt(4) = 2

sqrt(5) = 2

sqrt(10) = 3

Solution

binary search start + 1 < end is a template method, in the end, the start ajacent with end, so if end <= x return end or return start.

why check end <=x first becasue the end it's closing the x after do end * end so that 's the best solution.

class Solution:
    """
    @param x: An integer
    @return: The sqrt of x
    """
    def sqrt(self, x):
        if x <= 0:
            return 0
        start, end = 1, x

        while start + 1 < end:
            mid = (start + end) / 2
            if mid *  mid <= x:
                start = mid
            else:
                end = mid

        return start