专题三_二分_x 的平方根

一：题目

解释：返回x的算数平方根，如果是小数，则舍去小数部分，返回整数即可！

二：算法

①：暴力

从1开始求平方，最后要么直接找到一个值的平方为x，要么发现x在两个相邻的数的平方之间

暴力的时间复杂度为O(N)

但是我们从暴力得知，最后返回的一定是left，因为双指针相遇返回left和right都可以，但是如果发现x是两个相邻的数的平方之间，则返回left，因为题目要求向下取整

②：二分

做过了上道题目，此题简直如鱼得水！

我们将数组划分为两个部分，左部分值的平方<=x，右部分值的平方>x，本质是因为数组有可能没有直接平方等于x的值，所以左部分是<=

其次我们的区间的范围直接从1~x开始即可，因为只要一个数是正整数，则其一定小于其的平方！

所以：

mid*mid <=x 则left=mid  //落入左部分

mid*mid >x 则right=mid-1 //落入右部分

很显然，我们的求中点的式子必须为：mid = left + (right - left + 1) / 2！

因为，我们说过mid不能落在原地踏步的指针上，此题left=mid，所以不能落在left上，所以我们选择该式子，当只有两个元素的时候，mid会落在right指针上

其次循环的条件必定是left<right，避免双指针相遇再次进入循环，导致原地踏步死循环！

三：代码

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

解释：

1：循环条件，left<right

2：求中点式子，mid = left + (right - left + 1) / 2; 

3：返回的是left

4：x可能为0~1之间，所以一开始特判即可