| 标题： | Sqrt(x) |
| 通过率： | 22.9% |
| 难度： | 中等 |
Implement int sqrt(int x).
Compute and return the square root of x.
利用二分法查找。结果一定在0到x/2+1之间，然后继续找中间值mid，如果mid*mid>x说明结果一定在0到mid-1之间，反之则在mid+1到x/2+1
具体代码如下：中间值用long储存防止int越界：
1 public class Solution { 2 public int sqrt(int x) { 3 long min=0; 4 long max=x/2+1; 5 while(min<=max){ 6 long mid=(min+max)/2; 7 long res=mid*mid; 8 if(res==x)return (int)mid; 9 else if(res<x) min=mid+1; 10 else max=mid-1; 11 } 12 return (int)max; 13 } 14 }
原文：http://www.cnblogs.com/pkuYang/p/4361132.html