# Sqrt x ### Source - leetcode: [Sqrt(x) | LeetCode OJ](https://leetcode.com/problems/sqrtx/) - lintcode: [(141) Sqrt(x)](http://www.lintcode.com/en/problem/sqrtx/) ### 題解 - 二分搜索 由于只需要求整數部分，故對于任意正整數 xxx, 設其整數部分為 kkk, 顯然有 1≤k≤x1 \leq k \leq x1≤k≤x, 求解 kkk 的值也就轉化為了在有序數組中查找滿足某種約束條件的元素，顯然二分搜索是解決此類問題的良方。 ### Python ~~~ class Solution: # @param {integer} x # @return {integer} def mySqrt(self, x): if x < 0: return -1 elif x == 0: return 0 start, end = 1, x while start + 1 < end: mid = start + (end - start) / 2 if mid**2 == x: return mid elif mid**2 > x: end = mid else: start = mid return start ~~~ ### 源碼分析 1. 異常檢測，先處理小于等于0的值。 1. 使用二分搜索的經典模板，注意不能使用`start < end`, 否則在給定值1時產生死循環。 1. 最后返回平方根的整數部分`start`. 二分搜索過程很好理解，關鍵是最后的返回結果還需不需要判斷？比如是取 start, end, 還是 mid? 我們首先來分析下二分搜索的循環條件，由`while`循環條件`start + 1 < end`可知，`start`和`end`只可能有兩種關系，一個是`end == 1 || end ==2`這一特殊情況，返回值均為1，另一個就是循環終止時`start`恰好在`end`前一個元素。設值 x 的整數部分為 k, 那么在執行二分搜索的過程中 start≤k≤end start \leq k \leq endstart≤k≤end 關系一直存在，也就是說在沒有找到 mid2==xmid^2 == xmid2==x 時，循環退出時有 start<k<endstart < k < endstart<k<end, 取整的話顯然就是`start`了。 ### 復雜度分析 經典的二分搜索，時間復雜度為 O(logn)O(\log n)O(logn), 使用了`start`, `end`, `mid`變量，空間復雜度為 O(1)O(1)O(1). 除了使用二分法求平方根近似解之外，還可使用牛頓迭代法進一步提高運算效率，欲知后事如何，請猛戳 [求平方根sqrt()函數的底層算法效率問題 -- 簡明現代魔法](http://www.nowamagic.net/algorithm/algorithm_EfficacyOfFunctionSqrt.php)，不得不感嘆算法的魔力！