leetcode_69.x的平方根

题目如下 ：

看到题 ，我们最原始的想法就是暴力解决:

        for(long long i =0;i<=INT_MAX;i++){if(i*i==x){return i;}else if((i*i>x)&&((i-1)*(i-1)<x)){return i-1;}}

我们直接开始遍历，我们是整数的平方根，所以我们分两种情况讨论，一种是刚好等于x,一种是除不尽的。
对于刚好等于的我们直接返回 即可 ，对于有小数的我们就需要想一下了，例如 8 的 话 2 * 2等于4 3 * 3 等于9，那么根据题目我们就需要找到2和3，然后返回2作为答案，这样的话也是可以过的（不过需要注意的是 ，需要使用long long 哦，去最坏情况的话 i =INT_MAX也就是2的31次方减一，再做乘法的话会超出int的取值范围，造成 上溢的情况 ），不过算法复杂度是O(N)，有点高了，我们下来尝试着用二分法去优化一下。
二分的模板很多 ，选择适合自己的就好

这里我们使用左闭右闭的板子来写这个题

因为是左闭右闭，所以我们在设置初始值的时候令l = 0，r=INT_MAX；
开始二分 ，有的小伙伴肯定对二分的模板有疑问，例如while的条件应该写 小于还是小于等于呢？其实这跟选择有关系，看是选择左闭右闭还是 左闭右开
左闭右闭的话，那么我们应该是小于等于的，为什么呢？
因为我们选择了右端点，这时候左端点和右端点相等是有意义的。
下来我们开始二分，常规求mid，然后通过mid的值来判断该向哪边收缩

class Solution {
public:int mySqrt(int x) {long  long  l=0,r=INT_MAX;while(l<=r){long long  mid=(l+r)>>1;if(mid*mid>x){r=mid-1;}else  if(mid*mid<x){l=mid+1;}else{return mid;}}return  r;}
};

这里二分直接返回的是刚好相等的数，循环结束后返回的 r 才是小数的的答案

如图所示，这样其实是二分之后的位置，(因为我们是l<=r,所以当l和r相遇之后还会再来一次循环，例如我们找8的算数平方根，当 l==r 的时候，如上图 l==r==3 ，所以得出下一次的mid一定是3 3*3大于8，所以我们的 r 向前挪一步)根据题目要求得，我们应该返回 r 。