【题目描述】
给你一个非负整数 x
,计算并返回 x
的 算术平方根 。
由于返回类型是整数,结果只保留 整数部分 ,小数部分将被 舍去 。
注意:不允许使用任何内置指数函数和算符,例如 pow(x, 0.5)
或者 x ** 0.5
。
【测试用例】
示例1:
输入:x = 4
输出:2
示例2:
输入:x = 8
输出:2
解释:8的算术平方根是2.82842...,由于返回类型是整数,小数部分将被舍去。
【思路分析】
法一:暴力法
因为只用返回下取整的算术平方根,所以直接用一个变量 i 从1开始遍历就行,当 i*i > x的时候退出循环,返回 i - 1即可。
法二:二分法
首先定义左右边界,左边界left是0,右边界right是x/2+1(当x ≥ 4时,其算术平方根的范围是[0,x/2+1) ,这个定理应该是初高中定理),再看x=3,因为要下取整,所以算术平方根为1,也满足这个定理;x=2时,满足,而x=0和1时,其算术平方根就是本身,做特殊处理直接返回x就行。
定义循环条件为 left<=right ,这样返回时就返回right,因为退出循环的条件是left>right,又要下取整所以返回right。中间值mid = left + (right - left) / 2,这么写是因为如果写成mid = (left + right) / 2会出现溢出。
在循环体中,将 x / mid 与 mid 做比较,而不用mid * mid 与x作比较,这同样也是为了避免溢出。当 x / mid == mid 时:直接返回mid;
当 x / mid > mid 时:说明 mid*mid<x ,转到右区间查找,left = mid + 1;
当 x / mid < mid 时:说明 mid*mid>x,转到左区间查找,right = mid - 1;
最后直接返回right。
【参考代码】
法一:C实现
#include <stdio.h>
//easy-69-x的平方根
int mySqrt(int x);
int main(){
int x = 8;
int res = mySqrt(x);
printf("%d\n", res);
return 0;
}
//法一:暴力法
int mySqrt(int x) {
int i=1;
while(i*i <= x){
i++;
}
return i-1;
}
法一:C++实现
#include <iostream>
using namespace std;
//easy-69-x的平方根
class Solution {
public:
int mySqrt(int x);
};
//法一:暴力法
int Solution::mySqrt(int x){
long i = 1;
while(i*i <= x){
i++;
}
return i-1;
}
int main(){
int x = 8;
Solution sol;
int res = sol.mySqrt(x);
cout<<res<<endl;
return 0;
}
法二:C实现
#include <stdio.h>
//easy-69-x的平方根
int mySqrt(int x);
int main(){
int x = 8;
int res = mySqrt(x);
printf("%d\n", res);
return 0;
}
//法二:二分法
int mySqrt(int x) {
int left = 0;
int right = x / 2 + 1;
int mid;
if(x <= 1){
return x;
}
while(left <= right){
mid = left + (right - left) / 2;;
if(x / mid == mid){
return mid;
}else if(x / mid > mid){
left = mid + 1;
}else if(x / mid < mid){
right = mid - 1;
}
}
return right;
}
法二:C++实现
#include <iostream>
using namespace std;
//easy-69-x的平方根
class Solution {
public:
int mySqrt(int x);
};
//法二:二分法
int Solution::mySqrt(int x){
int left = 0;
int right = x / 2 + 1;
int mid;
if(x <= 1){
return x;
}
while(left <= right){
mid = left + (right - left) / 2;
if(x / mid == mid){
return mid;
}else if(x / mid > mid){
left = mid + 1;
}else if(x / mid < mid){
right = mid - 1;
}
}
return right;
}
int main(){
int x = 8;
Solution sol;
int res = sol.mySqrt(x);
cout<<res<<endl;
return 0;
}