Idea: Binary search. Let low variable start from 0, high variable start from x, test ((low+high)/2 )* ((low+high)/2). If smaller than x, increase low, otherwise decrease high.
Time: O(lgx) Space: O(1)
Code:
public class Solution {
public int sqrt(int x) {
long low=0;
long high=x;
while(low<=high)
{
long mid=(high+low)/2;
if(mid*mid==x)
return (int)mid;
if(mid*mid<x)
low=mid+1;
else
high=mid-1;
}
return (int)high;
}
}
No comments:
Post a Comment