二分查找法-LeetCode第69题:x 的平方根
前言
……还是一个学生,做题解只是个人记录,代码有不少错误或纰漏之处,还望多多包涵。
题目描述
实现 int sqrt(int x) 函数。
计算并返回 x 的平方根,其中 x 是非负整数。
由于返回类型是整数,结果只保留整数的部分,小数部分将被舍去。
示例 1:
输入: 4
输出: 2
示例 2:
输入: 8
输出: 2
说明: 8 的平方根是 2.82842…,
由于返回类型是整数,小数部分将被舍去。
第一次分析
计算平方根,看似比较简单的一道题,大体上可以想到思路为:从范围[1,x)中找到某个整数y,y的平方小于或等于x而y+1的平分大于x。
从一个有序序列中找一个数,我们自然而然地可以想到用二分查找法,但是有些细节问题需要考虑清楚。比如我们二分查找的循环条件一般是beg<end,那么循环结束后beg和end指向的是什么数?我们应该返回什么?我们找到的数大概率是不会刚好其平方就等于x的,那么弄清楚这些问题就尤为重要。
首先,我们要记住mid的两种计算方式:
mid = (beg + end) / 2; //此时mid会选择靠向beg这一边
mid = (beg + end + 1) / 2; //此时mid会选择靠向end这一边
记住这两点后,我们开始思考如何获取最后的y呢?
我们可以换个思路,在循环时,我们希望beg指向平方比x小的数,end指向平方比x大的数。在结束前,我们希望的理想状态是,beg指向y,end指向y+1。
此时会有两种情况出现:
1.我们令mid向beg靠拢,则最后mid会指向beg,计算mid得到的平方值肯定会小于x,因此我们移动不了end,只能移动beg令其指向end从而跳出循环。
2.我们令mid向end靠拢,则最后mid会指向end,计算mid得到的平方值肯定会大于x,因此我们移动不了beg,只能移动end令其指向beg从而跳出循环。
对于第一种情况,最后得到的应该是平方大于x的值,即y+1,因此我们应该返回beg-1。
第二种情况,最后得到的应该是平方小于x的值,即y,因此我们返回beg。
上代码:
class Solution {
public:
int mySqrt(int x) {
if(x == 0 || x == 1) //判断特殊情况
return x;
int beg = 1, end = x,result;
int mid = (beg + end) / 2; //mid向beg靠拢
while(beg < end)
{
result = mid * mid;
if(result < x) //beg向右侧靠拢,为最后指向end做准备
beg = mid + 1;
else if(result > x)
end = mid;
else
return mid; //结果相等,直接返回mid
mid = (beg + end) / 2;
}
return beg - 1; //此时beg平方大于x,因此应该返回beg-1
}
};
运行结果:
GG
第二次分析
为什么会出错?其实从报错提示来看已经很清楚了,没错,就是result溢出了。当我们的x很大时,初始mid值也会很大,这样的mid值相乘,肯定会造成溢出。
那可咋整呢?别急,我们可以把思维逆转过来,既然乘法会溢出,那用除法不就行了?我们用x除以mid,通过比较其与mid的大小作为二分条件。
这样就完了吗?还没有,还有个可能溢出的地方我们没有考虑到(没错,笔者又经历了一次执行错误),那就是初始的beg+end,也就是1+x。我们没有考虑到x是最大值的情况,这样1+x就溢出了。因此,虽然我们考虑的范围是[1,x),但我们实际上应该使用的范围是(0,x),从而保证其不溢出。其他操作和第一次分析一致。
代码如下:
class Solution {
public:
int mySqrt(int x) {
if(x == 0 || x == 1) //处理特殊情况
return x;
int beg = 0, end = x,result; //beg=0保证相加不溢出
int mid = (beg + end) / 2; //向beg靠拢
while(beg < end)
{
result = x / mid; //防止溢出
if(result == mid)
return mid;
if(result > mid)//beg向右侧靠拢,为最后指向end做准备
beg = mid + 1;
else
end = mid;
mid = (beg + end) / 2;
}
return beg - 1;//此时beg平方大于x,因此应该返回beg-1
}
};
运行结果:
顺利通过,OK!
顺便一提,我们刚刚用的是第一种做法,即beg向end靠拢的,我们也可以使用第二种,即end向beg靠拢,这两种操作是等价的,代码如下:
class Solution {
public:
int mySqrt(int x) {
if(x == 0 || x == 1)//处理特殊情况
return x;
int beg = 0, end = x,result;
int mid = (beg + end ) / 2;//这里不+1向end靠拢,是为了防止溢出
while(beg < end)
{
result = x / mid;
if(result == mid)
return mid;
if(result > mid)
beg = mid ;
else
end = mid - 1;//end向左侧靠拢,为最后指向beg做准备
mid = (beg + end + 1) / 2;//向end靠拢
}
return beg ;
}
};
运行结果:
顺利通过,OK!