69. Sqrt(x)

Typical binary search problem. The key is to find the right termination. Since sqrt(x) should return the bottom integer of the square root, we should use hi boundary because the hi boundary will be reduced 1 if mid square is larger than x.

1:  class Solution {  
2:  public:  
3:    int mySqrt(int x) {  
4:      if (x == 0 || x == 1) return x;  
5:      int lo = 0, hi = x/2;  
6:      while (lo <= hi) {  
7:        long long mid = lo + (hi - lo) / 2;  
8:        long long sqrt = mid * mid;  
9:        if (sqrt == x) return mid;  
10:        else if (sqrt > x) hi = mid-1;  
11:        else lo = mid+1;  
12:      }  
13:      return hi;  
14:    }  
15:  };  

When I revisited this problem, I had a bit more concise way. The idea behind is similar, but I observed that once r - l == 1 we've reached last two possible roots. l is moved to mid when mid*mid is less or equal to x, r is moved to mid when mid*mid is larger than x. So when r-l==1, l is the root that we'd like to find.

1:  class Solution {  
2:  public:  
3:    int mySqrt(int x) {  
4:      if (x == 0) return 0;  
5:      int l = 1, r = x;  
6:      while (l + 1< r) {  
7:        long long mid = l + (r-l)/2;  
8:        if (mid*mid > x) {  
9:          r = mid;  
10:        } else {  
11:          l = mid;  
12:        }  
13:      }  
14:      return l;  
15:    }  
16:  };