69 Sqrt(x)
Implement
int sqrt(int x).Compute and return the square root of x.
The Idea: The naive solution would be to return the first index in the for loop through x where
, since
. With binary search, the idea is the same except that we begin our search within the bounds of
[0, x], and eliminate the left or right half depending on whether the algorithm overestimated or underestimated the solution.Below, when
pow < x, we know this resulted in a underestimation so the next iteration will extend [mid+1, high].Complexity: O(log(x)) time and O(log(x)) space
int mySqrt(int x)
{
if (x == 0 || x == 1) return x;
long long start = 1, end = x, mid, pow, ans;
while (start <= end)
{
mid = (start + end) / 2;
pow = mid*mid;
if (pow == x) return mid;
else if (pow < x) {
start = mid + 1;
ans = mid;
}
else end = mid - 1;
}
return ans;
}
int main()
{
cout << mySqrt(2) << endl;
cout << mySqrt(1) << endl;
cout << mySqrt(2147483647) << endl;
}
Recursive Python Solution
import math
class Solution:
def mySqrt(self, x):
"""
:type x: int
:rtype: int
"""
def b_search(left, right):
mid = int(left + (right - left) / 2)
cur = math.pow(mid, 2)
over = math.pow(mid + 1, 2) # when this over estimates but cur does not, then we found our solution
if cur <= x < over:
return int(mid)
elif math.pow(mid, 2) > x: # over estimation
return b_search(left, mid - 1)
else:
return b_search(mid + 1, right) # under estimation
return b_search(0, x)
Last modified 4yr ago