Implement int sqrt(int x).
难度：76，用二分查找。要求是知道结果的范围，取定左界和右界，然后每次砍掉不满足条件的一半，知道左界和右界相遇。算法的时间复杂度是O(logx)，空间复杂度是O(1)。
1 public class Solution { 2 public int sqrt(int x) { 3 if (x < 0) { 4 return -1; 5 } 6 if (x == 0) { 7 return 0; 8 } 9 int l = 1; 10 int r = x/2 + 1; 11 while (l <= r) { 12 int m = (l + r)/2; 13 if (m <= x/m && x/(m+1) < m+1) return m; 14 else if (m > x/m) { 15 r = m - 1; 16 } 17 else { 18 l = m + 1; 19 } 20 } 21 return -1; 22 } 23 }
原文：http://www.cnblogs.com/EdwardLiu/p/3981176.html