【C++算法】20.二分查找算法_x 的平方根

题目链接：

69. x 的平方根

题目描述：

解法

暴力解法：

如果x=17

从1，2，3，4，5......这些数里面找他们的平方，16<x<25，所以整数部分是4

二段性：

可以使用二分查找

需要注意：0 <= x <= 2³¹ - 1

也就意味着x是可以比1小的，但这个时候直接就是0了。

C++ 算法代码：

暴力查找

class Solution {
    public:
    int mySqrt(int x) {
        // 由于两个较大的数相乘可能会超过 int 最大范围
        // 因此用 long long
        long long i = 0;
        for (i = 0; i <= x; i++)
        {
            // 如果两个数相乘正好等于 x，直接返回 i
            if (i * i == x) return i;
            // 如果第一次出现两个数相乘大于 x，说明结果是前一个数
            if (i * i > x) return i - 1;
        }
        // 为了处理oj题需要控制所有路径都有返回值
        return -1;
    }
};

二分查找

class Solution 
{
    public:
    int mySqrt(int x) 
    {
        if(x < 1) return 0; // 处理边界情况
        int left = 1, right = x; //从1-x二分
        while(left < right)
        {
            long long mid = left + (right - left + 1) / 2;
            if(mid * mid <= x) left = mid;
            else right = mid - 1;
        }
        return left;
    }
};

图解

例如：x=8

1. left=1，right=8

   进入循环，mid=1+(8-1+1)/2=1+4=5

2. left=1，right=4

   进入循环，mid=1+(4-1+1)/2=1+2=3

   right = mid - 1=2

3. left=1，right=2

   进入循环，mid=1+(2-1+1)/2=1+1=2

   mid * mid <= x，left = mid=2

4. left=2，right=2，不满足循环条件，return left;返回2。