69. Sqrt(x)

1.問題

• 實作sqrt

2.想法

• 提問

• function header, parameter

• test input

• 說明想法

  • edge case: x == 0

  • binary search

    • 初始狀態為left = 1, right = x

    • 當x / mid == mid, 回傳mid

    • 當x / mid > mid 時

      • 表示目標在mid右邊, 因此讓left = mid

      • 或是目標介於mid * mid與x間, 回傳mid

    • 當x / mid < mid時

      • 表示目標在mid左邊, 因此讓right = mid

      • 或是目標介於x 與 mid * mid間, 回傳x

• 測試計算複雜度

3.程式碼

class Solution {
public:
    int mySqrt(int x) {
        return binarySearch(1, x, x);
    }
private:
    int binarySearch(long left, long right, long target) {
        if (left > right) {
            return 0;
        }
        
        long mid = (left + right) / 2;
        long x = target / mid;
        
        if (mid == x) {
            return mid;
        }
        
        if (x > mid) {
            if (x - mid == 1) {
                return mid;
            }
            return binarySearch(mid + 1, right, target);
        } else {
            if (mid - x == 1) {
                return x;
            }
            return binarySearch(left, mid - 1, target);
        }
    }
};