题目描述

链接: 69. x 的平方根/Sqrt(x)

给你一个非负整数 x ，计算并返回 x 的算术平方根。
由于返回类型是整数，结果只保留整数部分，小数部分将被舍去。
注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。

题目分析：

题型：二分查找目标元素
关键：
- 二分查找的的关键、易错（避免死循环）均在【Leetcode每日一题】34.在排序数组中查找元素的第一个和最后一个位置|二分求下标、【Leetcode每日一题】35.搜素插入位置|二分查找数组下标两篇文章中详细讲到，这里不重复造轮子
- ⭐本题关键突破：二分查找区间：[0,x/2]。x/2>=根号x(只有x=0,和x=1特殊)/mid^2<=left,left=mid;—通过区间缩进，left不断逼近根号x（left^2<=x)
- 注意最后答案（这里记为ans)：ans*ans<=x(ans为整数）(本质类似于34题中的：求第一个等于target的元素，所用代码模板也是如出一辙）

代码分析：

❌错误代码分析：（2023/1/25）

class Solution {
    public int mySqrt(int x) {
        //特例判断，因为x/2>=根号x，在x>=2的时候成立
        if (x == 0) {
            return 0;
        } else if (x == 1) {
            return 1;
        }

        int left = 0;
        int right = x / 2;
        while (left < right) {
            int mid = left + (right - left + 1) / 2;//防止溢出

            if (mid * mid <= x) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }
}

2023/1/25：因为没有考虑乘法溢出：mid*mid<=x，当mid过大时乘法溢出。（一开始还忘记了在mid = left+(right-left+1);中的+1，导致了死循环，实在不该，谨记判断是否+1就看只剩两个元素时，mid的取值和区间划分能否缩小区间？若不能，必定死循环

✅正确代码：

class Solution {
    public int mySqrt(int x) {
        //特例判断，因为x/2>=根号x，在x>=2的时候成立
        if (x == 0) {
            return 0;
        } else if (x == 1) {
            return 1;
        }

        int left = 0;
        int right = x / 2;
        while (left < right) {
            int mid = left + (right - left + 1) / 2;//防止加法溢出
            if (mid <= x / mid) {//防止乘法溢出
                left = mid;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }
}

write in the end:

二分法系列题目：
【Leetcode每日一题】34.在排序数组中查找元素的第一个和最后一个位置|二分求下标
 【Leetcode每日一题】35.搜素插入位置|二分查找数组下标

建立此专栏的初衷是为了监督自己每天认真刷一个题，积少成多。并把自己每次刷题的思路、收获以博文的形式分享出来，帮助更多人，以及方便后续复习。如果有兴趣的同学可以订阅此专栏，我们一起刷题，一起交流，进步和学习！专栏：LeetCode每日一题–进击大厂