# 69. Sqrt(x) x 的平方根

@TOC

## # 题目描述

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.
``````

## # 解题方法

### # 方法一：库函数

``````import math
class Solution(object):
def mySqrt(self, x):
"""
:type x: int
:rtype: int
"""
return int(math.sqrt(x))
``````

### # 方法二：牛顿法

`f'(x) = -2x`.

`Xn+1 = Xn +(num - Xn ^ 2)/2Xn = (num + Xn ^ 2) / 2Xn = (num / Xn + Xn) / 2`.

`t = (num / t + t) / 2`.

``````class Solution(object):
def mySqrt(self, x):
"""
:type x: int
:rtype: int
"""
num = x
while num * num > x:
num = (num + x / num) / 2
return num
``````

### # 方法三：二分查找

``````def binary_searche(l, r):
while l < r:
m = l + (r - l) // 2
if f(m):    # 判断找了没有，optional
return m
if g(m):
r = m   # new range [l, m)
else:
l = m + 1 # new range [m+1, r)
``````

``````class Solution(object):
def mySqrt(self, x):
"""
:type x: int
:rtype: int
"""
left, right = 0, x + 1
# [left, right)
while left < right:
mid = left + (right - left) // 2
if mid ** 2 == x:
return mid
if mid ** 2 < x:
left = mid + 1
else:
right = mid
return left - 1
``````

``````class Solution(object):
def mySqrt(self, x):
"""
:type x: int
:rtype: int
"""
left, right = 0, x + 1 #[left, right)
while left < right:
mid = (left + right) // 2
if mid ** 2 == x:
return mid
elif (mid - 1) ** 2 < x and mid ** 2 >= x:
return mid - 1
elif mid ** 2 < x:
left = mid + 1
else:
right = mid
return left
``````

``````class Solution {
public:
int mySqrt(long long x) {
if (x == 0) return 0;
long long left = 0, right = x + 1; //[left, right)
while (left < right) {
long long mid = left + (right - left) / 2;
if (mid == x / mid) {
return mid;
} else if (mid < x / mid) {
left = mid + 1;
} else {
right = mid;
}
}
return left - 1;
}
};
``````

``````class Solution {
public:
int mySqrt(int x) {
if (x <= 1) return x;
int left = 0, right = x; //[left, right)
while (left < right) {
int mid = left + (right - left) / 2;
if (mid == x / mid) {
return mid;
} else if (mid < x / mid) {
left = mid + 1;
} else {
right = mid;
}
}
return left - 1;
}
};
``````

## # 日期

2018 年 2 月 4 日 2018 年 10 月 26 日 ——项目验收结束了！ 2018 年 11 月 27 日 —— 最近的雾霾太可怕