每日一练：二分查找-x的平方根

LCR 072. x 的平方根 - 力扣（LeetCode）

题目要求：

给定一个非负整数 x ，计算并返回 x 的平方根，即实现 int sqrt(int x) 函数。

正数的平方根有两个，只输出其中的正数平方根。

如果平方根不是整数，输出只保留整数的部分，小数部分将被舍去。

示例 1:

输入: x = 4
输出: 2

示例 2:

输入: x = 8
输出: 2
解释: 8 的平方根是 2.82842...，由于小数部分将被舍去，所以返回 2

提示:

• 0 <= x <= 2^31 - 1

暴力破解 O(N)：

        从0枚举到x，只要发现某个数 i 的平方小于等于x，并且 i+1 的平方大于x，那么 i 就是平方根。

class Solution {
public:
    int mySqrt(int x) {
        for(long long i = 0;i < x;i++){
            if(i*i<=x && (i+1)*(i+1)>x)
                return i;
        }
        return x;
    }
};

二分查找(查找左端点) O(LogN)：

        暴力破解中可以发现，如果x是8，那么结果2可以把数组分成左边：平方和小于8的部分和右边：平方和大于8的部分，可知数组具有二段性，所以可以使用二分查找。

        又因为可以舍去小数部分，即结果的平方和可能小于或者等于x，所以查找较小的左端点。

        注意：

        mid的平方可能大于INT_MAX，，所以用long long接收；

        因为查找的是左端点，对于偶数个数组，以中间偏右的元素为mid，否则left=mid可能造成死循环。

class Solution {
public:
    int mySqrt(int x) {
        int left = 0,right = x;
        while(left<right){
            long long mid = left+((long long)right-left+1)/2;
            if(mid*mid<x)
                left=mid;
            else if(mid*mid>x)
                right=mid-1;
            else // 优化：如果已经等于x，就不需要再找了
                return mid;
        }
        return left;
    }
};