题目描述:
Implement int sqrt(int x)
.
Compute and return the square root of x.
C语言版:
int mySqrt(int x) { int t, l, r, mid; l = 1; r = x>>1; if (x < 2) return x; while(l <= r){ mid = (l + r) >> 1; if (mid == x/mid) return mid; else if(mid < x/mid){ l = mid + 1; } else r = mid - 1; } return r; }看似一个简单的二分查找,其实里面也有很多细节要注意
比如:l的初始化问题,以前习惯性初始化为0,在这里就不可以,比如X==2的时候,会出现除0错误
还有就是一些开平方的结果是小数的,在这里当然就要输出整数,那么,最后return哪一个值呢?
一开始我固执的以为应该是左边的指针较小,应该返回左边的指针l,错了才发现,跳出循环的时候
左边的指针已经大于右边的指针了,因此应该返回右边的指针r!