題目會給定一個輸入整數x，要求我們返回x的正整數平方根(取無條件捨去小數部分的正整數值)
測試範例:
Example 1:
Input: x = 4
Output: 2
Explanation: The square root of 4 is 2, so we return 2.
Example 2:
Input: x = 8
Output: 2
Explanation: The square root of 8 is 2.82842..., and since we round it down to the nearest integer, 2 is returned.
約束條件:
Constraints:
0 <= x <= 231- 1
演算法:
這題除了傳統正規的"牛頓逼近法"可以去計算平方根之外，
也可以使用之前學過的二分搜尋法來找。
二分搜尋法本身就適用於在已經排序好(不論遞增或遞減)的數列裡面做搜尋。
因為y = sqrt(x) 本身也是一個連續函數曲線，而且嚴格遞增。
y = sqrt(x) 的函數圖
所以我們可以令
初始左端點為0，右端點為x，每次用二分搜尋法，去尋找x的正整數平方根。(取無條件捨去小數部分的正整數值)
程式碼:
class Solution:
def mySqrt(self, x: int) -> int:
left, right = 0, x
while left <= right:
mid = left + (right - left) // 2
square = mid * mid
if square <= x:
left = mid + 1
elif square > x :
right = mid -1
return left-1
時間複雜度:
O( log n ) 每次削去一半不可能的區間，最多O(log n)回合可以找到答案。
遞迴關係式 T(n) = T(n/2) + O(1)
空間複雜度:
O( 1 ) 只有使用固定大小的臨時變數，占用的記憶體空間為常數級別O(1)。
學完這題，記得和最一開始的那一題 Binary Search 二分搜尋，做個對照喔，彼此的觀念和演算法原理都是相通的。
關鍵都在於每次取中心點，用二分法去逼近解答或者目標值。
Reference:
[1] Python O( log n ) sol. based on binary search - Sqrt(x) - LeetCode
