题目：
Implement int sqrt(int x).
Compute and return the square root of x.
链接： http://leetcode.com/problems/sqrtx/
2/14/2017, Java，不是自己想的。。。
二分法，需要进行第3行的判断
1 public class Solution { 2 public int mySqrt(int x) { 3 if (x <= 1) return x; 4 5 int lo = 0, hi = x; 6 int mid; 7 8 while( lo <= hi) { 9 mid = lo + (hi - lo) / 2; 10 if (mid < x / mid) { 11 lo = mid + 1; 12 } else if (mid > x / mid) { 13 hi = mid - 1; 14 } else { 15 return mid; 16 } 17 } 18 return hi; 19 } 20 }
牛顿法，肯定也不是自己想的。
还是注意input = 1的情况
1 public class Solution { 2 public int mySqrt(int x) { 3 if (x <= 1) return x; 4 5 double lastY = x / 2; 6 double Y = (lastY + x / lastY) / 2; 7 8 while (Y != lastY) { 9 lastY = Y; 10 Y = (lastY + x / lastY) / 2; 11 } 12 return (int)Y; 13 } 14 }
原文：http://www.cnblogs.com/panini/p/6400691.html