69. Sqrt(x)
給定一個非負整數 x，返回 x 的平方根並向下取整到最接近的整數。返回的整數也應該是非負的。
你不能使用任何內置的指數函數或運算符。
例如，在 C++ 中不要使用 pow(x, 0.5) 或在 Python 中不要使用 x ** 0.5。
範例 1：
輸入：x = 4 輸出：2 解釋：4 的平方根是 2，所以我們返回 2。
Python
class Solution:
def mySqrt(self, x: int) -> int:
if x < 2:
return x
left, right = 1, x // 2
while left <= right:
mid = (left + right) // 2
if mid * mid == x:
return mid
elif mid * mid < x:
left = mid + 1
else:
right = mid - 1
return right
16.41MB, 43ms
C++
class Solution {
public:
int mySqrt(int x) {
if (x < 2) {
return x;
}
int left = 1, right = x / 2, result = 0;
while (left <= right) {
int mid = left + (right - left) / 2;
if (mid <= x / mid) {
result = mid; // Update result to the current mid
left = mid + 1;
} else {
right = mid - 1;
}
}
return result;
}
};
7.42MB, 2ms
Javascript
/**
* @param {number} x
* @return {number}
*/
var mySqrt = function(x) {
if (x < 2) {
return x;
}
let left = 1, right = Math.floor(x / 2);
let result = 0;
while (left <= right) {
let mid = Math.floor((left + right) / 2);
if (mid * mid <= x) {
result = mid; // Update result to the current mid
left = mid + 1;
} else {
right = mid - 1;
}
}
return result;
};
51.68MB, 69ms
