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

Challenge

O(log(x))

Solution

Time: O(log N), Space: O(1)
Binary search [0,x] find m (m*m==x)

(SqrtX.py) download

class Solution:
    """
    @param x: An integer
    @return: The sqrt of x
    """
    def sqrt(self, x):
        # write your code here
        front = 0
        end = x
        if x == 0 or x == 1:
            return x
        result = 0
        while front <= end:
            mid = (front+end)/2
            if mid*mid == x:
                return mid
            elif mid*mid > x:
                end = mid-1
            else:
                front = mid+1
        # x=2147483647, return 46340
        return front-1