---
# System prepended metadata

title: LeetCode 69. Sqrt(x)
tags: [Leetcode]

---

# LeetCode 69. Sqrt(x)
[LeetCode question name](leetcode_url) (難度 通過率)
<!-- 
(<font color=#00AF9B>Easy</font> 53.8%) 
(<font color=#FFB800>Medium</font> 39.6%)
(<font color=#FF375F>Hard</font>)
 -->
    
- 限制 :

    <ul>
    <li><code>0 <= x <= 2^31 - 1</code></li>
    </ul>

- Solution

    這一題要 lg(n) 成立要 mid*mid 的數值變化是 binary tree。
    - 時間複雜度: $O(lg(n))$
    - 空間複雜度: $O(1)$

- 程式碼
    ```c++=
    class Solution {
    public:
        int mySqrt(int x) {
            if(x==0) return 0;
            long min_num = 0, max_num =x, mid = (max_num-min_num)/2 + min_num;
            while(min_num<=max_num)
            {
                mid = (max_num-min_num)/2 + min_num;
                if(mid*mid < long(x)) min_num = mid + 1;
                else max_num = mid - 1;
            }
            for(long i = long(max(max_num,min_num));i>=0;i--)
            {
                if(i*i <= long(x)) return i;
            }
            return 0;
        }
    };
    ```
</details>