바이너리 서치를 사용했다.
class Solution {
public int mySqrt(int x) {
Long l = 0L;
Long r = new Long(x);
Long result = 0L;
while(l <= r) {
Long mid = (l + r) / 2;
Long val = mid * mid;
if(val > x) {
r = mid - 1;
}
else if(val == x) {
return mid.intValue();
}
else{
result = mid;
l = mid + 1;
}
}
return result.intValue();
}
}
class Solution:
def mySqrt(self, x: int) -> int:
l = 0
r = x
result = 0
while l <= r:
mid = (l+r) // 2
val = mid * mid
if val > x:
r = mid - 1
elif val == x:
return mid
else:
result = mid
l = mid + 1
return result