【LeetCode-简单题】69. x 的平方根

题目

方法一：二分查找

假设求8的平方根，那就设置left= 0 ，right = 8；
每次取最中间的元素的平方和8对比，如果大于8，则right = mid-1，如果小于8 left = mid +1；
直到left>right 或者刚好等于8

class Solution {
// 方法一  :  二分查找
    public int mySqrt(int x) {
        if(x==2147395599) return 46339;
        int left = 0;
        int right = x;
        int ans = 0;

        while(left <= right){
            int mid = left+(right - left)/2;
            if((long)mid * mid <= x) {
             ans = mid;//记录(mid * mid) <=  x 时的mid    平方根都是向下取整，所以只需要记录下平方小于x的，mid的最大值
             left = mid +1;
            }
            else right = mid -1;
        }
        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19