69 Sqrt(x) – Medium
Problem:
Implement int sqrt(int x).
Compute and return the square root of x.
Thoughts:
The most straight forward way it so iterate over all possible numbers, namely 1 to x/2+1.
But we could find it faster by using binary search. improving running time from O(x) to O(logx).
Plus, the condition to determine result is also critical, because we cannot say m*m == x is the checking condition.
Solutions:
public class Solution {
public int mySqrt(int x) {
int left = 1, right = x/2;
while ( left <= right) {
int mid = (left + right) /2;
if (mid > x /mid) {
right = mid - 1;
continue;
}
if ((mid+1) <= x/(mid+1)) {
left = mid + 1;
continue;
}
return mid;
}
return x;
}
}