Leetcode - sqrt(x)

[分析]
这是一道数值计算的题目，Code Ganker中指出数值计算类型题目通常就是二分法或者以2为基进行位处理。此题使用二分法，实现套路就是最经典的二分算法。数值计算题需要特别注意的就是数值越界处理。此题一开始没写对就是处理大数据时溢出，Method 1就是溢出版本，mid 为 int 类型，如果没有强转类型，则 mid * mid的结果仍然是int类型，赋给long类型的midSquare是不能防止数值溢出的。正如算平均数时使用减号避免加和溢出一样，可以使用除法来避免乘法溢出。
leetcode中其他数值计算题：pow(x,n)，Divide Two Integers

[ref]
http://blog.csdn.net/linhuanmars/article/details/20089131

public class Solution {
    // Method 2
    public int mySqrt(int x) {
        if (x <= 0)
            return 0;
        int left = 1, right = x / 2 + 1;
        int mid = 0;
        while (left <= right) {
            mid = left + ((right - left) >> 1);
            if (mid <= x / mid && (x / (mid + 1)) < mid + 1) {
                return mid;
            } else if (mid > x / mid) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return 0;
    }
    // Method 1: fail @2147395599
    public int mySqrt1(int x) {
        if (x <= 0)
            return 0;
        int left = 1, right = x / 2 + 1;
        int mid = 0;
        while (left <= right) {
            mid = left + ((right - left) >> 1);
            long midSquare = mid * mid;
            if (midSquare <= x && x < (mid + 1) * (mid + 1))
                return mid;
            else if (midSquare > x)
                right = mid - 1;
            else
                left = mid + 1;
        }
        return right;
    }
}