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

本文介绍: 给你一个非负整数x，计算并返回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;
    }
};