Sqrt(x)

Source

• lintcode: 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))

题解

start要从1开始

Python

class Solution:
    """
    @param x: An integer
    @return: The sqrt of x
    """
    def sqrt(self, x):
        # write your code here
        if x<0:
            return -1
        if x==0:
            return 0

        start=1
        end=x

        while True:
            mid=(start+end)/2

            if mid>x/mid:
                end=mid-1
            else:
                if (mid+1)>x/(mid+1):
                    return mid
                else:
                    start=mid+1