【LeetCode刷题笔记（六十一）】之 69. x的平方根

素颜马尾好姑娘i 2023-10-07 15:17 184阅读 0赞

### 本文章由公号【开发小鸽】发布！欢迎关注！！！ ###

**老规矩–妹妹镇楼：**

![20200721223424816.JPG][]

### 一． 题目 ###

#### （一） 题干 ####

实现 int sqrt(int x) 函数。

计算并返回 x 的平方根，其中 x 是非负整数。

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

#### （二） 示例 ####

示例 1:

输入: 4
    输出: 2

示例 2:

输入: 8
    输出: 2
    说明: 8 的平方根是 2.82842..., 
         由于返回类型是整数，小数部分将被舍去。

### 二． 题解 ###

#### （一） 思路 ####

实现平方根函数，返回平方根的整数部分。这种题目使用二分法来解决，不断地寻找中间数来比较它的平方与x的关系，如果它的平方大于x，说明要寻找的数比该数还要小，因此缩小右边界，继续寻找；如果它的平方小于x，说明要寻找的数可能比该数要大，注意我这里说的是可能，因为该数有可能就是x的平方根的整数部分，因此，只要是该数的平方<=x的，都要当做最后的输出记录下来；如果它的平方等于x，则直接找出了最终结果。

按照这种思路进行迭代，最终得到输出的结果。

#### （二） 代码实现 ####

Java：

class Solution {
        
        public int mySqrt(int x) {
        
            // x >= 0
            //使用二分法来解决, 在 0 - x的范围内
            int left = 0, right = x, ans = -1;
            while(left <= right){
        
                int mid = left + (right-left)/2;
                if((long)mid*mid < x){
        
                    ans = mid;
                    left = mid+1;
                }else if((long)mid * mid == x){
        
                    ans = mid;
                    return ans;
                }else{
        
                    right = mid-1;
                }
            }
            return ans;
    
        }
    }

[20200721223424816.JPG]: https://img-blog.csdnimg.cn/20200721223424816.JPG