题目描述

题目链接：69.x的平方根

算法原理

解法一：暴力查找

依次枚举 [0, x] 之间的所有数 i （这⾥没有必要研究是否枚举到 x / 2 还是 x / 2 + 1 。因为我们找到结果之后直接就返回了，往后的情况就不会再判断。反⽽研究枚举区间，既耽误时间，⼜可能出错）

• 如果 i * i == x ，直接返回 x ；
• 如果 i * i > x ，说明之前的⼀个数是结果，返回 i - 1 。

由于 i * i 可能超过 int 的最⼤值，因此使⽤ long long 类型

解法二：二分查找

设 x 的平⽅根的最终结果为 index ，分析 index 左右两边区间数据的特点：

• [0, index] 之间的元素，平⽅之后都是⼩于等于 x 的；
• [index + 1, x] 之间的元素，平⽅之后都是⼤于 x 的。

因此可以使⽤⼆分查找算法。

代码实现

暴力查找

class Solution {
public:int mySqrt(int x) {// 由于两个较⼤的数相乘可能会超过 int 最⼤范围// 因此⽤ long longlong long i = 0;for (i = 0; i <= x; i++) {// 如果两个数相乘正好等于 x，直接返回 iif (i * i == x)return i;// 如果第⼀次出现两个数相乘⼤于 x，说明结果是前⼀个数if (i * i > x)return i - 1;}// 为了处理oj题需要控制所有路径都有返回值return -1;}
};

C++

class Solution {
public:int mySqrt(int x) {// 处理边界情况if (x < 1)return 0;// 二段性使用二分int left = 1, right = x;while (left < right) {// 防溢出long long mid = left + (right - left + 1) / 2;if (mid * mid <= x)left = mid;elseright = mid - 1;}return left;}
};

Java

class Solution {public int mySqrt(int x) {// 细节if (x < 1)return 0;long left = 1, right = x;while (left < right) {long mid = left + (right - left + 1) / 2;if (mid * mid <= x)left = mid;elseright = mid - 1;}return (int) left;}
}