题解 | #求平方根#二分法

二分法，然后挨着比，不要用 mid*mid，会溢出，用 x/mid 即可

python实现

class Solution:
    def sqrt(self , x: int) -> int:
        # write code here
        if x == 1:
            return 1
        left, right = 1, x
        while left <= right:
            mid = (left + right)//2
            if mid<=(x//mid) and (mid+1) > x//(mid+1):  #在中间了
                return mid
            elif mid > (x//mid):  # mid太大，往左半边走
                right = mid-1
            else:              # mid太小，往右半边走
                left = mid+1
        return 0

c++实现

class Solution {
public:
    int sqrt(int x) {
        // write code here
        int left=1, right=x, mid;
        while(left <= right){
            mid = (left + right)/2;
            if(mid <= (x/mid) && (mid+1) > (x/(mid+1))){
                return mid;
            }else{
                if(mid > (x/mid)){
                    right = mid-1;
                }else{
                    left = mid+1;
                }
            }
        }
        return 0;
    }
};