LeetCode 69. Sqrt(x)

Implement int sqrt(int x).

Compute and return the square root of x.

x is guaranteed to be a non-negative integer.

Example 1:

Input: 4
Output: 2

Example 2:

Input: 8
Output: 2
Explanation: The square root of 8 is 2.82842..., and since we want to return an integer, the decimal part will be truncated.


要求编程实现sqrt（）函数，比较高效的方法是使用二分搜索，不难证明，对于一个整数n，其平方根所在的范围为[0,n/2+1]，所以需要在此区间内进行二分查找，代码如下

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

时间复杂度：O(logn)

空间复杂度：O（1）

当然也可以用牛顿下降法求解，详细请移步：

http://www.cnblogs.com/AnnieKim/archive/2013/04/18/3028607.html

http://www.cnblogs.com/grandyang/p/4346413.html

一刷：各种出错，首先要注意使用long long类型，否则会溢出；其次是要注意返回 j 而不是 i ，以为当平方根不为整数，需要舍弃小数部分，也就是向下取整