LintCode Python 简单级题目 14.x的平方根

题目描述：

实现 int sqrt(int x) 函数，计算并返回 x 的平方根。

您在真实的面试中是否遇到过这个题？

Yes

样例

sqrt(3) = 1

sqrt(4) = 2

sqrt(5) = 2

sqrt(10) = 3

挑战

O(log(x))

标签

数学二分法脸书

题目分析：

class Solution:
    """
    @param x: An integer
    @return: The sqrt of x
    """
    def sqrt(self, x):
        # write your code here
        begin = 0
        end = x
        if x == 0: return 0
        if x == 1: return 1
        
        while True:
            mid = (begin+end)/2
            if mid**2 == x: 
                return mid
            # x处于[begin,end]中间的一个数
            # 如果mid**2 < x，且(mid+1) **2 >x，则mid为最接近于x的平方根
            if mid**2 < x and (mid+1)**2 > x:
                return mid
            elif mid**2 < x:
                begin = mid
                end = end
                continue
            else:
                begin = begin
                end = mid
                continue