Problem

Implement int sqrt(int x).

Compute and return the square root of x.

Example

sqrt(3) = 1

sqrt(4) = 2

sqrt(5) = 2

sqrt(10) = 3

Note

非常好的练习二分法的题目。
使用夹逼法，a^2 <= x < (a+1)^2，则a为所求。
注意溢出，要灵活应用除法。

Solution

1. start <= end / start < end / start + 1 < end

class Solution {
    public int sqrt(int x) {
        if (x < 1) return 0;
        int start = 1;
        int end = x;
        while (start < end) {
            int mid = start + (end-start)/2;
            if (mid <= x/mid && mid+1 > x/(mid+1)) {
                return mid;
            } // The key to success
            if (mid <= x/mid) start = mid;
            else end = mid;
        }
        return start;
    }
}
   

1. start+1 < end

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