69. Sqrt(x)

Implement int sqrt(int x).

Compute and return the square root of x.

Approach:

This problem isn't difficult; binary search 1-x will suffice. There are a few details to be aware of.

1. To find the median value, use start + (end - start) / 2, not (start + end) / 2, to avoid the sum of start + end exceeding the range.
2. Don't use `mid*mid == x` either; use `mid = x/mid` instead, for the same reason as above.

public class Solution { public int mySqrt(int x) { int start=1; int end = x; if(x<2) return x; while(start x / (mid + 1)){ return mid; } if(mid > x / mid){ end =mid; } else{ start =mid+1; } } return -1; } }