- 博主简介：努力学习的预备程序媛一枚~
- 博主主页： @是瑶瑶子啦
- 所属专栏: LeetCode每日一题–进击大厂
题目描述
给你一个非负整数 x ，计算并返回 x 的 算术平方根 。
由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。
注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。
题目分析：
- 题型：二分查找目标元素
- 关键：
- 二分查找的的关键、易错（避免死循环）均在【Leetcode每日一题】34.在排序数组中查找元素的第一个和最后一个位置|二分求下标、【Leetcode每日一题】35.搜素插入位置|二分查找数组下标两篇文章中详细讲到，这里不重复造轮子
- ⭐本题关键突破：二分查找区间：[0,x/2]。
x/2>=根号x(只有x=0,和x=1特殊)/mid^2<=left,left=mid;—通过区间缩进，left不断逼近根号x（left^2<=x) - 注意最后答案（这里记为ans)：
ans*ans<=x(ans为整数）(本质类似于34题中的：求第一个等于target的元素，所用代码模板也是如出一辙）
代码分析：
❌错误代码分析：（2023/1/25）
class Solution {
public int mySqrt(int x) {
//特例判断，因为x/2>=根号x，在x>=2的时候成立
if (x == 0) {
return 0;
} else if (x == 1) {
return 1;
}
int left = 0;
int right = x / 2;
while (left < right) {
int mid = left + (right - left + 1) / 2;//防止溢出
if (mid * mid <= x) {
left = mid;
} else {
right = mid - 1;
}
}
return left;
}
}
- 2023/1/25：因为没有考虑乘法溢出：
mid*mid<=x，当mid过大时乘法溢出。（一开始还忘记了在mid = left+(right-left+1);中的+1，导致了死循环，实在不该，谨记判断是否+1就看只剩两个元素时，mid的取值和区间划分能否缩小区间？若不能，必定死循环 
✅正确代码：
class Solution {
public int mySqrt(int x) {
//特例判断，因为x/2>=根号x，在x>=2的时候成立
if (x == 0) {
return 0;
} else if (x == 1) {
return 1;
}
int left = 0;
int right = x / 2;
while (left < right) {
int mid = left + (right - left + 1) / 2;//防止加法溢出
if (mid <= x / mid) {
//防止乘法溢出
left = mid;
} else {
right = mid - 1;
}
}
return left;
}
}
write in the end:
- 二分法系列题目：
【Leetcode每日一题】34.在排序数组中查找元素的第一个和最后一 个位置|二分求下标
【Leetcode每日一题】35.搜素插入位置|二分查找数组下标- 建立此专栏的初衷是为了监督自己每天认真刷一个题，积少成多。并把自己每次刷题的思路、收获以博文的形式分享出来，帮助更多人，以及方便后续复习。如果有兴趣的同学可以订阅此专栏，我们一起刷题，一起交流，进步和学习！专栏：LeetCode每日一题–进击大厂
转载：https://blog.csdn.net/Yaoyao2024/article/details/128762817
查看评论