题解 | #求平方根#

举个例子：9二分，我们就取中间，向下取整的话就可以用整除//，然后取中为4,4的平方为16大于了9，所以范围到【0，4】；然后同理二分为2,又平方小于9，然后范围取【2,4】。所以return了3.

#
# 
# @param x int整型 
# @return int整型
#
import math
class Solution:
    def mysqrt(self , x ):
        # write code here
# 简单就是直接引入math函数
#         return int(math.mysqrt(x))
# 但这道算法题是考察二分
        if x==0:
            return 0
        if x==1:
            return 1
        if x ==2:
            return 1
        else:
            lower = 0
            a = 0
            upper = x
            while True:
                mid = (upper+lower) //2 
                if mid*mid <=x:
                    if (mid+1)*(mid+1) > x:
                        a = mid
                        return a 
                    else:
                        lower = mid
                else:
                    upper = mid