leetcode 69. x 的平方根（优质解法）

代码：

class Solution {
    public int mySqrt(int x) {
        long left=0;
        long right=x;

        while (left<right){
            long mid=left+(right-left+1)/2;
            //注意乘法操作和加法操作都很容易发生溢出
            if(mid*mid<=x){
                left=mid;
            }else {
                right=mid-1;
            }
        }

        return (int)left;
    }
}

题解：

? ? ? ? 本题的题意表述得很清晰，x 是一个非负整数，我们要算出 x 的平方根，当平方根是小数时，要把小数部分省略

? ? ? ? 首先我们可以想到一个暴力解法，x 的平方根肯定是小于等于 x 的，所以我们只需要遍历 0 - x 的数，找到 x 的平方根即可

? ? ? ? 比如 x = 4，我们需要遍历 0，1，2，3，4，当 i = 2 时，2*2 =4 ，得到结果 2

0????????1????????2????????3????????4

? ? ? ? ? ? ? ? ? ? ?i? ??

? ? ? ? 比如 x =8 ，我们需要遍历 0，1，2，3，4，5，6，7，8 当 i =2 时，2*2 = 4 < 8,我们向前遍历，当 i = 3 时，3*3 = 9 > 8 ,所以我们得到 2?

0????????1????????2????????3????????4????????5????????6????????7????????8

? ? ? ? ? ? ? ? ? ? ?i?

? ? ? ? ? 我们可以将? 0，1，2，3，4 和? 0，1，2，3，4，5，6，7，8 这两个区间进行划分，【0，1，2】是i 的平方<= x 的区间，【3，4】是 i 的平方 > x 的区间； 【?0，1，2】是 i 的平方 <= x 的区间【3，4，5，6，7，8】是 i 的平方 > x 的区间

? ? ? ? 我们可以看出，结果都是?<= x 的区间的右边界，当选取一个数位于?<= x 的区间，那么这个数左边的数便可以排除掉（不能排除该数，因为不确定该数是否就是我们要找的右边界），如果一个数位于 > x 的区间，那么这个数以及右边的数都可以排除掉

? ? ? ? 通过上述分析我们就知道应该用二分法来解决这个问题

? ? ? ? 以 x = 8 为例

? ? ? ? L 和 R 指针的下标就对应要遍历的值，首先获取中间值 mid = L+（R-L+1）/2 = 4，4*4 =16 位于 > x 的区间，我们就可以大胆去除 mid 及其右边的所有数，让 R 指针指向 mid -1 的位置

0? ? ? ? 1? ? ? ? 2? ? ? ? 3? ? ? ? 4? ? ? ? 5? ? ? ? 6? ? ? ? 7? ? ? ? 8

L? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?mid? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?R?

? ? ? ? 获取中间值 mid = 2，此时 2*2 =4 < 8,位于 <= x 的区间，所以我们可以大胆去除 mid 左边的数（不能去除 mid ，因为不确定 mid 的值是不是我们要找的值），让 L = mid

0? ? ? ? 1? ? ? ? 2? ? ? ? 3? ? ? ? 4? ? ? ? 5? ? ? ? 6? ? ? ? 7? ? ? ? 8

L? ? ? ? ? ? ? ? ?mid? ? ?R

? ? ? ? 再取中间值，mid =3，位于 > x 的区间，我们让 R = mid-1

0? ? ? ? 1? ? ? ? 2? ? ? ? 3? ? ? ? 4? ? ? ? 5? ? ? ? 6? ? ? ? 7? ? ? ? 8

????????? ? ? ? ? ? ?L? ? ? ? R

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? mid

? ? ? ? 当 L 和 R 指针相遇时，我们便得到了相要获得的数

0? ? ? ? 1? ? ? ? 2? ? ? ? 3? ? ? ? 4? ? ? ? 5? ? ? ? 6? ? ? ? 7? ? ? ? 8

????????? ? ? ? ? ? ?L? ? ? ??

? ? ? ? ? ? ? ? ? ? ?R??