69. Sqrt(x) - Easy

前往題目

想法

• Binary Search

思路

1. 在0~x之間搜尋
2. 如果當前位置平方小於x那就往右繼續找
3. 如果大於，就往左邊(更小的數字)找
4. 最後收斂的位置左邊就是答案，因為無條件捨去小數

Code

class Solution {
    public int mySqrt(int x) {
        if (x == 0) return 0;
        if (x == 1) return 1;

        int l = 0, r = x;

        // Search the answer
        while (l <= r) {
            // Possible answer
            int mid = l + (r - l) / 2;
            // Current num * num
            long tmp = (long) mid * (long) mid;
            
            // When this number ^ 2 is smaller than the target, we continue search on its right
            if (tmp < (long) x) {
                l = mid + 1;
            } else if (tmp > (long) x) {
                r = mid - 1;
            } else { // Found the exact answer
                return mid;
            }
        }
        // Round down to the nearest integer
        return l - 1;
    }
}