Implement int sqrt(int x).
Compute and return the square root of x.
Analysis:
Using binary search to find the solution. However, what need to be consider is when x is large, some k=(begin+end)/2 may be overflow, as a result, we cannot get the right answer. When calculating k*k, we need cast k to (double) type.
Solution:
1 public class Solution { 2 public int sqrt(int x) { 3 if (x==0 || x==1) return x; 4 5 int z = x; 6 int y = 1; 7 int k = -1; 8 while (true){ 9 k = y+(z-y)/2; 10 double temp = (double) k*(double)k; 11 if (temp==x) 12 return k; 13 else if (temp>x){ 14 z = k; 15 continue; 16 } else if ((double)(k+1)*(double)(k+1)>x){ 17 return k; 18 } else { 19 y = k; 20 continue; 21 } 22 } 23 24 25 } 26 }
原文：http://www.cnblogs.com/lishiblog/p/4102728.html