69. Sqrt(x)

Leetcode Math Binary Search

Implement int sqrt(int x).

Compute and return the square root of $x$, where $x$ is guaranteed to be a non-negative integer.

Since the return type is an integer, the decimal digits are truncated and only the integer part of the result is returned.

Example 1:

Input: 4
Output: 2

Example 2:

Input: 8
Output: 2
Explanation: The square root of 8 is 2.82842..., and since 
             the decimal part is truncated, 2 is returned.

分析

这道题目可以使用二分查找，唯一需要注意的就是整数值可能过大，所以这里当计算平方的时候采用double类型防止两个整数相乘溢出。

public int mySqrt(int x) {
    int lo = 1, hi = x;
    while (lo <= hi) {
        int mid = (lo + hi) >>> 1;
        double cmp = ((double) mid)* mid - x;
        if (cmp > 0) hi = mid - 1;
        else if (cmp < 0) lo = mid + 1;
        else return mid;
    }
    return lo - 1;
}

在比较数字的时候，采用除法更好一些，避免了int类型的转换，和double类型的保存:

public int mySqrt(int x) {
    int lo = 1, hi = x;
    while (lo <= hi) {
        int mid = (lo + hi) >>> 1;
        int cmp = mid - x/mid;
        if (cmp > 0) hi = mid - 1;
        else if (cmp < 0) lo = mid + 1;
        else return mid;
    }
    return lo - 1;
}