69. x 的平方根
文章目录
- 1.题目
- 2.思路
- 3.代码
1.题目
69. x 的平方根
给你一个非负整数 x ，计算并返回 x 的 算术平方根 。
由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。
**注意：**不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。
示例 1：
输入：x = 4
输出：2
示例 2：
输入：x = 8
输出：2
解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。
2.思路
- 初始化左边界
left为 0，右边界right为x，用于定义搜索范围。 - 通过二分查找的方式，计算中间值
mid，并求出mid的平方square。 - 如果
square等于x，直接返回mid，因为它就是x的整数平方根。 - 如果
square大于x，说明当前的mid太大，更新右边界right = mid - 1，继续在较小的范围内搜索。 - 如果
square小于x，说明当前的mid太小，更新左边界left = mid + 1，继续在较大的范围内搜索。 - 当搜索结束时，返回
right，它是平方小于或等于x的最大整数，即x的整数平方根。
3.代码
class Solution {
public:int mySqrt(int x) {long long left = 0, right = x;while(left<=right){long long mid = left+(right-left)/2;long long square = mid*mid;if(square == x){return mid;}else if(square>x){right = mid-1;}else{left = mid+1;}}return right;}
};