Thinking process

analyze the input and ouput

• if negative numbers or 0 return x

Using binary search

• how to find the one? num * num < x
• don't use Math.sqrt in this question!

Mistakes

start, end and mid should be long, since it might be overflow if using mid * mid > x

otherwise use x / mid as condition to check

class Solution {
    /**
     * @param x: An integer
     * @return: The sqrt of x
     */
    public int sqrt(int x) {
        // write your code here
        if (x <= 0) return x;

        int start = 1;
        int end = x;

        while (start + 1 < end) {
            int mid = (end - start) / 2 + start;

            if (mid == x / mid) {
                return mid;
            } else if (mid < x / mid) {
                start = mid;
            } else {
                end = mid;
            }
        }

        if (end < x / end) {
            return end;
        }

        return start;
    }
}