leetcode69
程序员文章站
2022-03-19 11:57:14
...
使用二分查找求小于某个数字的平方根的最大整数
思路:使用二分查找减少查找时间,要每次记录mid的值,否则left和right可能会大于或者小于真正的结果值
class Solution {
public int mySqrt(int x) {
if(x == 0||x == 1) return x;
int left = 1,right = x,res = -1;
while(left <= right) {
int mid = left + (right - left)/2;
if((long) mid*mid <= x) {
res = mid;
//找到了一个可能解,小于x的都是可能的情况
//但需要找到可能情况中的最大值,而left记录
//的可能比最大值要大,因此,要记录每次的mid
left = mid + 1;
}
else
right = mid - 1;
}
return res;
}
}
上一篇: LeetCode【69】 Sqrt(x)
推荐阅读