[LeetCode] Sqrt(x)

Implement int sqrt(int x).

Compute and return the square root of x.

解法：二分搜索

　　时间复杂度O(logN), 空间复杂度O(1)

 1 class Solution {
 2 public:
 3     int mySqrt(int x) {
 4     int low = 0;
 5     int high = x / 2 + 1;
 6     while (low <= high)
 7     {
 8         long long mid = low + (high - low) / 2;
 9         long long sq = mid * mid;
10         if (sq == x) {
11             return mid;
12         } else if (sq < x) {
13             low = mid + 1;
14         } else {
15             high = mid - 1;
16         }
17     }
18     return high;
19     }
20 };

补充资料：http://www.cnblogs.com/AnnieKim/archive/2013/04/18/3028607.html