69. Sqrt(x)
in Coding Interview on Math, Binary Search
음수가 아닌 정수 x가 주어지면 가장 가까운 정수로 내림한 x의 제곱근을 반환
class Solution {
// 음수가 아닌 정수 x가 주어지면 가장 가까운 정수로 내림한 x의 제곱근을 반환합니다.
// O(log n)
public int mySqrt(int x) {
if (x == 0 || x == 1) return x;
int left = 0, right = x;
while (left < right) {
// mid = (left + right) / 2 can overflow if right > Integer.MAX_VALUE - left
int mid = left + (right - left) / 2;
// same thing here , mid * mid > x can overflow. replace by mid > x / mid
if (mid > x / mid) {
right = mid - 1;
} else {
left = mid + 1;
// if mid * mid < x but (mid + 1) * (mid + 1) > x then mid was the right answer
if (left > x / left) {
return mid;
}
}
}
return left;
}
}