Sqrt(x)

来源：Leetcode

原帖：http://oj.leetcode.com/problems/sqrtx/

题目：
Implement int sqrt(int x). Compute and return the square root of x.

思路：
这道题用binary search搞定。需要注意的是函数签名，在面试中遇到过两种。int sqrt(int); double sqrt(double). 如果输入是int，在进行binary search的时候可能会遇到overflow。 输入是double，需要考虑<1, >1的情况，另外需要考虑double精度问题。

代码：
1] int type input

 class Solution {  
 public:  
     int sqrt(int x) {  
         assert(x >= 0);  
         int l = 0, r = x / 2 + 1;  
         while (l + 1 < r) {  
             // long long mid = l + (r - l) / 2; // overflow problem.   
             // long long sq = mid * mid;  
             // if (sq == x) {  
             //   return mid;  
             // } else if (sq < x) {  
             //   l = mid;  
             // } else {  
             //   r = mid;  
             // }  
   
             int mid = l + (r - l) / 2;  
             int quot = x / mid;  
             if (quot == mid) {  
                 return quot;  
             } else if (quot > mid) {  
                 l = mid;  
             } else {  
                 r = mid;  
             }  
         }  
         if (r * r == x) return r;  
         return l;  
     }  
 };  

2] input is double

 class Solution {  
 public:  
     const double eps = 1.0e-12;  
     // 0 means equal, -1 means smaller, +1 means larger  
     int compare(double a, double b) {  
         if (a == 0) a += eps;  
         if (b == 0) b += eps;  
         double diff = (a - b) / b;  
         return diff > eps ? 1 : diff < -eps ? -1 : 0;  
     };  
   
     double square_root(double x) {  
         // Decide the search range according to x  
         double l, r;  
         if (compare(x, 1.0) < 0) { // x < 1.0  
             l = x; r = 1.0;  
         } else { // x >= 1.0  
             l = 1.0; r = x;  
         }  
         // Keep searching if l < r  
         while (compare(l, r) < 0) {  
             double m = l + 0.5 * (r - l);  
             double square_m = m * m;  
             if (compare(square_m, x) == 0) {  
                 return m;  
             } else if (compare(square_m, x) < 0) {  
                 l = m;  
             } else {  
                 r = m;  
             }  
         }  
         return l;  
     }  
 };