package binary_search;

/**

* Created by gouthamvidyapradhan on 22/05/2017.

* Implement int sqrt(int x).

* <p>

* Compute and return the square root of x.

*/

public class SqrtX {

public static void main(String[] args) throws Exception {

System.out.println(new SqrtX().mySqrt(Integer.MAX_VALUE));

}

public int mySqrt(int x) {

int s = 0, e = x;

long ans = 0L;

while (s <= e) {

long m = s + (e - s) / 2;

long prod = m * m;

if (prod <= x) {

s = (int) (m + 1);

ans = m;

} else e = (int) m - 1;

}

return (int) ans;

}

}