examination questions
Implement int sqrt(int x).
Compute and return the square root of x.
Example
sqrt(3) = 1
sqrt(4) = 2
sqrt(5) = 2
sqrt(10) = 3
Challenge
O(log(x))
解题代码
class Solution {
public:
/**
* @param x: An integer
* @return: The sqrt of x
*/
int sqrt(int x) {
if (x == ){
return ;
}
long long int temp = x / ;
int deposit;
while (true){
if (temp * temp > x){
deposit = temp;
temp = temp / ;
}
else{
if ((temp + )*(temp + ) > x){
return temp;
}
else{
temp = (deposit + temp) / ;
}
}
}
}
};
算法分析
使用二分法，给定一个要求的数，然后分半，若该数的平方大于给定的数，则对该数进行平分，如果平分后的平方小于给定的数，那么取该数与平分前的数的中数进行平方，每一次平方后如果该数是大于给定的数的，那么检测与该数小1的数的平方是否小于给定的数，如果是，那么该数为结果。
代码解析
class Solution {
public:
/**
* @param x: An integer
* @return: The sqrt of x
*/
int sqrt(int x) {
if (x == ){ //如果为1，那么直接得出结果
return ;
}
long long int temp = x / ; //二分
int deposit; //用于二分前的值，存放
while (true){
if (temp * temp > x){ //大于就二分
deposit = temp; //存放
temp = temp / ; //二分
}
else{
if ((temp + )*(temp + ) > x){ //如果+1的平方大于x的话，那么就是该值
return temp;
}
else{
temp = (deposit + temp) / ; //二分前与二分后的中值
}
}
}
}
};