[leetcode] SqrtX

package leetcode;

/**
* <pre>
* Implement int sqrt(int x).
*
* Compute and return the square root of x.
* </pre>
* */
public class SqrtX {
    public static class Solution {
        public int sqrt(int x) {

            long start = 0;
            long end = (long) Integer.MAX_VALUE + 1;

            //start*start<=x<end*end
            while (true) {
                long mid = start + (end - start) / 2;

                if (mid * mid > x) {
                    end = mid;
                    continue;
                }

                if ((mid + 1) * (mid + 1) > x)
                    return (int) mid;

                start = mid;
            }
        }
    }

}