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

发布时间:2024年01月06日

前言

这是道简单题

一、题目链接

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

文章来源:https://blog.csdn.net/lrsnt/article/details/135429254
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。