runtime 0 ms, beats 100% of cpp submissions
O(log(n)) solution with explanation

tags: binary search

Sqrt(x)

📖 description

給定一個整數，回傳開根號後的結果，如果遇到非完全平方數，則對結果取 floor，不能使用內建函數。

ex 1.
    Input: x = 4

    Output: 2

    Explanation: 
        The square root of 4 is 2, so we return 2.



ex 2.
    Input: x = 8

    Output: 2

    Explanation: 
        The square root of 8 is 2.82842..., and since we round it down to the nearest integer, 2 is returned.

🧠 solution

最暴力的作法是直接從 x 往下搜尋，直到找到符合的數字，但雖然題目沒有提到 sorted 等字眼，但整個數列其實可以視為排序過的結果，所以問題就是該如何決定搜尋區間。

  • 如果 mid 為 0 ，向右搜尋
  • 如果 mid x mid 比 x 小，向右找符合條件，但更大的解
  • 否則向左搜尋

⏳ time complexity

對 [1~x] 區間進行 binary search ，時間複雜度 O(log(n))
總時間複雜度 O(log(n))

📝 code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int mySqrt(int x) {
        int l = 0,r = x,ans = 0;
        while(r>=l){
            int mid = (l+r)/2;
            if(mid == 0){           // 避免除以 0 的情況
                l = mid+1;
            }
            else if(mid <= x/mid){  // 避免運算出現溢位
                ans = mid;          // 保存成一組解
                l = mid+1;
            }
            else{
                r = mid-1;
            }
        }
        return ans;
    }
};