LeetCode-69. x 的平方根

不念不忘少年蓝@ 2024-03-23 11:29 3阅读 0赞

#### 目录 ####

*   *  题目思路
     *  代码实现

题目来源  
[69. x 的平方根][69. x]

### 题目思路 ###

从题目的要求和示例我们可以看出，这其实是一个查找整数的问题，并且这个整数是有范围的。

*  如果这个整数的平方 恰好等于 输入整数，那么我们就找到了这个整数；
 *  如果这个整数的平方 严格大于 输入整数，那么这个整数肯定不是我们要找的那个数；  
    我们要求的整数位8，但是3的平方为9，那么就不是我们找的数
 *  如果这个整数的平方 严格小于 输入整数，那么这个整数 可能 是我们要找的那个数。

因此我们可以使用「二分查找」来查找这个整数，不断缩小范围去猜。

猜的数平方以后大了就往小了猜；  
猜的数平方以后恰恰好等于输入的数就找到了；  
猜的数平方以后小了，可能猜的数就是，也可能不是。

### 代码实现 ###

class Solution {
        
        public int mySqrt(int x) {
        
            if(x == 0){
        
                return 0;
            }
            if(x == 1){
        
                return 1;
            }
            long left = 0;
            long right = x / 2;
            while(left <= right){
        
                long mid = left + ((right-left)>>1);
                long square = mid * mid;
                if(square>x){
        
                    right = mid-1;
                }else if(square < x){
        
                    left = mid + 1;
                }else{
        
                    return (int)mid;
                }
            }
            return (int)(left-1);
        }
    }

![在这里插入图片描述][f1f7a36cebab4c24821fc830a80a587e.png]

[69. x]: https://leetcode.cn/problems/sqrtx/
[f1f7a36cebab4c24821fc830a80a587e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/69fb05d7d8b84303b1782f1a0edeff3d.png