63 x的平方根

题目

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

由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。

注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。

示例 1：

输入：x = 4
输出：2
示例 2：

输入：x = 8
输出：2
解释：8 的算术平方根是 2.82842…, 由于返回类型是整数，小数部分将被舍去。

提示：

0 <= x <= 231 - 1

• 法一：二分法

class Solution {
public:
    int mySqrt(int x) {
    	//如果right为x/2，则当x值为1时，会直接跳过while循环，right值为0，会返回错误答案
        int left=1,right=x/2+1;
        //x的平方根一定在[1,x/2]之间
        //一定要是<=，如果x值为0，此时left为1，right为1，如果跳过while循环会返回错误答案
        while(left<=right)
        {
            int mid=left+(right-left)/2;
            if(x/mid>mid)//防止数字超过int范围
            {
                left=mid+1;//取右区间
            }else if(x/mid<mid){
                right=mid-1;//取左区间
            }else{
                return mid;//等于mid则表示找到了答案
            }
        }
        return right;//退出循环时left=right+1
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

• 思路：类似二分查找
  • 不断在left和right区间内找目标值
  • 注意while的判断条件与left、right的初始值有关，此处选择左闭右闭区间
  • 正常退出while循环时返回右边界，可带入特殊值辅助判断