二分查找-69.x的平方根-力扣(LeetCode)

白天的黑夜

发布于 2025-10-22 17:06:33

5600

代码可运行

文章被收录于专栏：leetcode题目解析和知识分享leetcode题目解析和知识分享

运行总次数：0

代码可运行

一、题目解析

1.结果只保留整数部分，小数部分舍去

2.不允许使用任何内置指数函数和算符

二、算法原理

解法1：暴力解法

从1开始枚举出平方数，与x比较大小

解法2：二分算法

二段性

根据举例可以发现，要找的平方根，它的平方数是小于或等于x的，因此我们可以划分出两段区间，由此可以使用二分算法解决问题

这里mid的计算是防止int的溢出

细节问题

1.由于x范围属于[0,2^31-1]，对于x<1的情况单独处理，因为x<1，所以x的平方根同样<1，由于小数部分要被舍弃，所以结果为0

2.这里的mid*mid会超出int存储大小，所以可以用long long

三、代码示例

解法2：

class Solution {
public:
    int mySqrt(int x)
    {
        if(x<1) return 0;
        int left = 1,right = x;
        while(left<right)
        {
            long long mid = left + (right - left + 1)/2;//防止溢出
            if(mid*mid <= x) left = mid;
            else right = mid - 1;
        }
        return left;
    }
};