The regular one is fairly straight-forward. Go as close as possible and return a number <= the sq root.

```
public int mySqrt_slow(int x) {
if(x<=1) {
return x;
}
long res = 0;
int max = Integer.MIN_VALUE;
while(res<=x/2) {
if(res*res>(long)x) {
break;
}
max = Math.max((int)res,max);
res++;
}
return max;
}
```

Alternative is to use a binary search. Use long to avoid overflows. The idea is to pick a number that is half of the previous. If nothing works, return the last high.

```
public int mySqrt(int x) {
if(x<=1) {
return x;
}
int l = 1;
int h = x/2;
while(l<=h) {
int p = (h-l)/2+l;
if((long)p*p==(long)x) {
return p;
}
else if((long)p*p>(long)x) {
h=p-1;
}
else {
l=p+1;
}
}
return h;
}
```