【题解】leetcode---69. x 的平方（二分查找入门）

前言

这是道简单题

一、题目链接

69. x 的平方根 - 力扣（LeetCode）

二、题目简介

给你一个非负整数x，计算并返回x的算术平方根。

三、涉及知识点

long long型数据处理、求取中值、正难则反（求解思路）

四、算法分析

知识点：二分算法

详解：

不能用函数计算x的算术平方根，则反过来，求一个数的平方等于x。

题目转换成找到第一个平方 等于目标x的数，或者是平方最接近x的小于x的数（一些整数的平方根存在有小数点的情况，无法完全等于）

从小到大寻找，寻找的数组成有序数组，使用二分法优化时间复杂度

左指针从1开始，代表数字1，右指针从x开始。

当mid的平方小于等于x时，left = mid （因为此时的mid可能就是结果，所以不能+1）

若mid的平方大于 x 时 ， right = mid-1 （此时不可能为结果所以-1）

当left >right时结束 （left>right不能加等号，在上面的二分规则下，若循环判断加了等号，会陷入死循环）

left所指即为结果

五、源码讲解

class Solution {
public:
    int mySqrt(int x) {
        //处理边界
        if(x < 1)
        {
            return 0; //因为x小于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;
    }
};

六、FAQ

1. mid = left + (right - left+1)/2 与 mid = left + (right - left)/2的区别？

当左右指针内包含的数为偶数个时，前者指向右边，后者指向左边。

如 1 ，2 ，left = 1，right = 2的情况下，前者的运算mid指向2，后者的mid指向1

在本题中使用前者，当left和right维护的数只剩两个时，left所指就是答案。此时要让循环停止，只能移动right，而right的移动需要mid的平方大于x，所以就要让mid指向更大的那个数，即右边的数，所以使用左边的求中值的规则。

其实还有个方法判断使用哪一种规则，就是当二分算法中出现-号时，上面的mid计算式就要有+1，这个是经验总结出来的。比如本题中right = mid -1；含有减号，所以mid的计算要含有+1