解題說明
Valid Perfect Square
題目描述：
給定正整數 num，不使用內建的平方根函數，判斷 num 是否為完全平方數。
解題思路：
使用二分搜尋在 [1, num] 範圍內尋找一個整數 mid 使得 mid * mid == num。
- 設定
left = 1，right = num。 - 取中間值
mid，計算mid * mid：- 若等於
num，回傳 true。 - 若小於
num，搜尋右半段left = mid + 1。 - 若大於
num，搜尋左半段right = mid - 1。
- 若等於
- 若搜尋結束仍未找到，回傳 false。
注意使用 long long 避免 mid * mid 溢位。
C++ 解法
複雜度分析
時間複雜度：O(log n) — 標準二分搜尋，每次將搜尋範圍縮小一半。
空間複雜度：O(1) — 只使用常數個變數。
虛擬碼
1. Initialize left = 1, right = num 2. While left <= right: a. mid = left + (right - left) / 2 b. square = mid * mid c. If square == num: return true d. If square < num: left = mid + 1 e. Else: right = mid - 1 3. Return false
其他解法
牛頓迭代法 O(log n)：從初始猜測 x = num 開始，反覆更新 x = (x + num / x) / 2 直到 x * x <= num。收斂速度為二次方（每次迭代有效位數加倍），實際上比二分搜尋更快。但需要注意整數除法的向下取整行為。
奇數累加法 O(sqrt(n))：完全平方數等於前 k 個奇數的和：1 + 3 + 5 + ... + (2k-1) = k²。依序減去奇數 1, 3, 5, ...，若 num 減為 0 則為完全平方數。直觀但效率不如二分搜尋。
延伸思考
- 如何用牛頓法求整數平方根？（LeetCode 69）與此題的二分法有何異同？
- 為什麼
mid * mid需要用long long？在什麼範圍的 num 下會發生溢位？ - 若要判斷一個數是否為完全 k 次方數（如立方數），如何修改此算法？