【二分查找】Leetcode x 的平方根
题目解析
69. x 的平方根
这道题表面是没有顺序性，但是我们可以发现如果使用枚举策略，它是包含顺序性质的，因此我们将枚举算法改进成二分算法
算法讲解
我们让left指针指向1， right指针指向x
如果当前的mid计算出来的平方 > x，right = mid - 1;
else left = mid;
这里需要注意的一点是，我们这里的mid计算需要使用left + (right - left + 1) / 2
class Solution {
public:int mySqrt(int x) {//这道题没有直接的顺序性，但是我们可以寻找顺序性if(x == 0)return 0;int left = 1, right = x;while(left < right){long long mid = left + (right - left + 1) / 2;long long num = pow(mid, 2);if(num > x)right = mid - 1;else left = mid;}return left;}
};