29. Divide Two Integers
题目描述：
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.
题目翻译
实现 int sqrt(int x).
计算并返回x的平方根.
x 保证是一个非负整数.
样例 1:
输入: 4
输出: 2
样例 2:
输入: 8
输出: 2
Explanation: The square root of 8 is 2.82842..., and since we want to return an integer, the decimal part will be truncated.
说明：8的平方根是2.82842...,因为我们要返回一个整数,所以小数部分将被舍去.
解题方案
标签： Binary Search
思路：
二进制搜索的思路很基础，较为简单，只给出代码. 我们还可以使用牛顿迭代法：若要计算x2 = n的解，设f(x)=x2-n，相当于求解f(x)=0的解，使用牛顿迭代法不断求导，利用切线逼近f(x)=0的解，最后得到答案
代码：(二进制搜索)
class Solution {
public:
int mySqrt(int x) {
if (0 == x) return 0;
int left = 1, right = x, ans;
while (left <= right) {
int mid = left + (right - left) / 2;
if (mid <= x / mid) {
left = mid + 1;
ans = mid;
} else {
right = mid - 1;
}
}
return ans;
}
};
代码：(牛顿迭代法)
class Solution {
public:
int mySqrt(int x) {
if(x<2) return x;
long r = x/2;
while (r*r > x)
r = (r + x/r) / 2;
return r;
}
};