# 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)$

- 程式碼

    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>