# Sqrt(x)

## Question

### Problem Statement

Implement int sqrt(int x).

Compute and return the square root of x.

## 题解 - 二分搜索

### Python

class Solution(object):
def mySqrt(self, x):
"""
:type x: int
:rtype: int
"""
if x < 0:
return -1
elif x == 0:
return 0

lb, ub = 1, x
while lb + 1 < ub:
mid = (lb + ub) / 2
if mid**2 == x:
return mid
elif mid**2 < x:
lb = mid
else:
ub = mid

return lb


### C++

class Solution {
public:
int mySqrt(int x) {
if (x < 0) return -1;
if (x == 0) return 0;

int lb = 1, ub = x;
long long mid = 0;
while (lb + 1 < ub) {
mid = lb + (ub - lb) / 2;
if (mid * mid == x) {
return mid;
} else if (mid * mid < x) {
lb = mid;
} else {
ub = mid;
}
}

return lb;
}
};


### Java

public class Solution {
public int mySqrt(int x) {
if (x < 0) return -1;
if (x == 0) return 0;

int lb = 1, ub = x;
long mid = 0;
while (lb + 1 < ub) {
mid = lb + (ub - lb) / 2;
if (mid * mid == x) {
return (int)mid;
} else if (mid * mid < x) {
lb = (int)mid;
} else {
ub = (int)mid;
}
}

return (int)lb;
}
}


### 源码分析

1. 异常检测，先处理小于等于0的值。
2. 使用二分搜索的经典模板，注意不能使用lb < ub, 否则在给定值1时产生死循环。
3. 最后返回平方根的整数部分lb.
4. C++ 代码 mid 需要定义为long long，否则计算平方时会溢出，定义 mid 放在循环体外部有助于提升效率。