题解 | #求平方根#

二分查找

#
# 
# @param x int整型 
# @return int整型
#
class Solution:
    def sqrt(self , x ):
        # write code here
        if x <= 1:
            return x
        lo, hi = 0, x
        mid = lo + (hi-lo)/2
        while lo < hi:
            mid = lo + (hi-lo)/2
            if mid*mid == x:                
                return mid
            elif mid*mid < x:
                lo = mid+1
                if (mid+1)*(mid+1) >= x:
                    return mid 
            elif mid*mid > x:
                hi = mid-1
                if (mid-1)*(mid-1) <= x:
                    return mid-1 
        return mid