Open Cosen95 opened 4 years ago
这道题目采用二分查找
即可解决。但是有两个点需要注意:
>>
替代/2
操作(更加准确)middle > x / middle
替代middle*middle > x
操作(防止溢出)
/**
* @param {number} x
* @return {number}
*/
var mySqrt = function(x) {
if(x == 0 || x ==1){
return x;
}
var left = 1;
var right = x;
while(left <= right){
var middle = left + ((right-left)>>1);
if(middle == x / middle){
return middle;
}else if(middle > x / middle){
right = middle-1;
}else{
left = middle+1;
}
}
// 结束条件是right < left 这里取较小值,也就是right
return right;
};
leetcode: https://leetcode-cn.com/problems/sqrtx/