LeetCode 69. Sqrt(x)

[Woodyiiiiiii]

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.

---

最简单的方法，从1开始遍历，直到平方大于x：

// O(n)
class Solution {
    public int mySqrt(int x) {
        if (x <= 1) return x;
        long i = 1, mul = i * i;
        while (mul <= x) {
            ++i;
            mul = i * i;
        }
        return (int)(i - 1);
    }
}

时间复杂度可以缩小至O(lgn)，使用二分法:

class Solution {
    public int mySqrt(int x) {
         if(x == 1){
            return 1;
        }
        int left = 1;
        int right = x / 2;
        int maxNumber = 0;
        while (left <= right) {
            long mid = left + (right - left) / 2;
            if (mid * mid <= x) {
                maxNumber = (int) mid;
                left = (int) (mid + 1);
            } else if (mid * mid > x) {
                right = (int) mid - 1;
            }

        }
        return maxNumber;
    }
}

---

参考资料：

• https://leetcode.com/problems/sqrtx/