Sqrt x

Question

  • leetcode: Sqrt(x) | LeetCode OJ
  • lintcode: (141) Sqrt(x)

題解 - 二分搜索

由於只需要求整數部分，故對於任意正整數 x, 設其整數部分為 k, 顯然有 1 \leq k \leq x, 求解 k 的值也就轉化為了在有序陣列中查找滿足某種約束條件的元素，顯然二分搜索是解決此類問題的良方。

Python

  1. class Solution:
    2.     # @param {integer} x
    3.     # @return {integer}
    4.     def mySqrt(self, x):
    5.         if x < 0:
    6.             return -1
    7.         elif x == 0:
    8.             return 0
    9.   10.         start, end = 1, x
    11.         while start + 1 < end:
    12.             mid = start + (end - start) / 2
    13.             if mid**2 == x:
    14.                 return mid
    15.             elif mid**2 > x:
    16.                 end = mid
    17.             else:
    18.                 start = mid
    19.   20.         return start

源碼分析

  1. 異常檢測，先處理小於等於0的值。
  2. 使用二分搜索的經典模板，注意不能使用start < end, 否則在給定值1時產生死循環。
  3. 最後返回平方根的整數部分start.

二分搜索過程很好理解，關鍵是最後的返回結果還需不需要判斷？比如是取 start, end, 還是 mid? 我們首先來分析下二分搜索的循環條件，由while循環條件start + 1 < end可知，start和end只可能有兩種關系，一個是end == 1 || end ==2這一特殊情況，返回值均為1，另一個就是循環終止時start恰好在end前一個元素。設值 x 的整數部分為 k, 那麼在執行二分搜索的過程中 start \leq k \leq end 關系一直存在，也就是說在沒有找到 mid^2 == x 時，循環退出時有 start < k < end, 取整的話顯然就是start了。

C++

  1. class Solution{
    2. public:
    3.     int mySqrt(int x) {
    4.         if(x <= 1) return x;
    5.         int lo = 2, hi = x;
    6.         while(lo < hi){
    7.             int m = lo + (hi - lo)/2;
    8.             int q = x/m;
    9.             if(q == m and x % m == 0)
    10.                 return m;
    11.             else if(q < m)
    12.                 hi = m;
    13.             else
    14.                 lo = m + 1;
    15.         }
    16.   17.         return lo - 1;
    18.     }
    19. };

源碼分析

此題依然可以被翻譯成”找不大於target的x^2”，而所有待選的自然數當然是有序數列，因此同樣可以用二分搜索的思維解題，然而此題不會出現重複元素，因此可以增加一個相等就返回的條件，另外這邊我們同樣使用[lo, hi)的標示法來處理邊界條件，可以參照[Search for a range]，就不再贅述。另外特別注意，判斷找到的條件不是用m * m == x而是x / m == m，這是因為x * x可能會超出INT_MAX而溢位，因此用除法可以解決這個問題，再輔以餘數判斷是否整除以及下一步的走法。

複雜度分析

經典的二分搜索，時間複雜度為 O(\log n), 使用了start, end, mid變量，空間複雜度為 O(1).
除了使用二分法求平方根近似解之外，還可使用牛頓迭代法進一步提高運算效率，欲知後事如何，請猛戳 求平方根sqrt()函數的底層算法效率問題 — 簡明現代魔法，不得不感歎演算法的魔力！