题目描述:
- Implement int sqrt(int x).
- Compute and return the square root of x.
- x is guaranteed to be a non-negative integer.
思路: 二分查找, 时间复杂度 O(logn)
if(mid 的平方等于 x 或者 mid 的平方小于 x 且 mid+1 的平方大于 x) return mid;
可能溢出的地方:
1(left+right)/2 因为 (left+right) 可能大于 Integer.MAX_VALUE
解决方案:(left+right)/2 ==> left + (right-left)/2;
2mid*mid (mid+1)*(mid+1)
解决: if(mid*mid==x) ==> if(mid==x/mid)
来源: http://www.bubuko.com/infodetail-2546052.html