算法精粹(algorithm-essentials)

感谢soulmachine@github提供内容
## Sqrt(x)

### 描述

Implement int `sqrt(int x)`.

Compute and return the square root of `x`.


### 分析

二分查找


### 代码

```cpp
// LeetCode, Sqrt(x)
// 二分查找
// 时间复杂度O(logn),空间复杂度O(1)
class Solution {
public:
int mySqrt(int x) {
int left = 1, right = x / 2;
int last_mid; // 记录最近一次mid

if (x < 2) return x;

while(left <= right) {
const int mid = left + (right - left) / 2;
if(x / mid > mid) { // 不要用 x > mid * mid,会溢出
left = mid + 1;
last_mid = mid;
} else if(x / mid < mid) {
right = mid - 1;
} else {
return mid;
}
}
return last_mid;
}
};
```

### 相关题目

* [Pow(x)](pow.md)