Implement int sqrt(int x).
Compute and return the square root of x.
此题看着简单，实则坑爹啊！！！！！
首先，关于平方，int是不够用的。
其次，二分法肯定好用，但是，最终的结果怎么取？原则上取小于等于的最近整数。但是mid的计算可能会更改这个数，所以需要调整一下。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24 |
class
Solution {public: int
sqrt(int
x) { long
long left = 0; long
long right = x; long
long mid = left + (right - left)/2; while(left < right) { if(mid * mid > x) { right = mid -1; } else
if(mid * mid < x) { left = mid +1 ; } else
return mid; mid = left + (right - left)/2; } if(left * left > x)return
left -1; return
left; }}; |
原文：http://www.cnblogs.com/pengyu2003/p/3620974.html