专题三x的平方根

1.题目

题目分析：
给一个非负的整数，然后要开根号，返回正数的，还要向下取整，小数部分就要被舍弃掉。

2.算法原理

因为是整数，所以可以把x到1的数铺开，因为合适的值左边是小于合适值，右边是大于合适值，就有了二段性，就可以用二分查找，拿mid*mid来比较，需要注意两个数字相乘可能会溢出，所以用long long类型，如果ret小于等于x，则left=mid，而不是mid+1，是因为mid肯定是小于x，且可能本来是合适值+1后就不是了，就会陷入死循环，如果大于就right=mid-1，而right可以-1是因为循环条件是left<right,当遇到只有俩个的时候就会陷入死循环，所以需要-1，避免陷入死循环。这里-1和+1d都需要仔细思考，来避免进入死循环，然后min=left+(right-left+1)/2是为了俩个点的情况下取右边也是避免死循环，虽然是先写min值，但是后面的代码决定了min的形式。

3.代码实现

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