一魚多吃 用 二分搜尋的觀念，來解 Sqrt(x) 整數平方根 Leetcode #69

這題的題目在這裡

題目會給定一個輸入整數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