LeetCode 训练场：69. x 的平方根

1. 题目

69. x 的平方根

2. 描述

实现 int sqrt(int x) 函数。 计算并返回 x 的平方根，其中 x 是非负整数。 由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。 示例 1: 输入: 4 输出: 2 示例 2: 输入: 8 输出: 2 说明: 8 的平方根是 2.82842…, ​ 由于返回类型是整数，小数部分将被舍去。

3. 实现方法

3.1 方法 1

3.1.1 思路

1. 二分查找
2. 由于 x 的平方根的整数部分 res 是满足 res * res <= x 的最大值，因此对 res 进行二分查找；
3. 确定上下界 low、high，然后比较中间元素 mid 的平方和 x 的大小， 通过结果调整上下界范围；
4. 此时的时间复杂度为需要二分查找的次数，为

；

3.1.2 实现

public int mySqrt(int x) {
    int low = 0;
    int high = x;
    int res = 0;

    while(low <= high){
        int mid = low + (high - low) / 2;
        if(x >= (long) mid * mid){
            res = mid;
            low = mid + 1;
        }else{
            high = mid - 1;
        }
    }

    return res;
}