二分法
二分法的特點
依賴于遞回演算法，逐次將區間長度減半，直至無限逼近所求點的方法，
演算法的復雜度與區間長度，精度，待求點的位置分布有關
LeetCode 69
實作 int sqrt(int x) 函式，
計算并回傳 x 的平方根，其中 x 是非負整數，
由于回傳型別是整數，結果只保留整數的部分，小數部分將被舍去，
示例
輸入: 4
輸出: 2
輸入: 8
輸出: 2
解題思路
class Solution(object):
def dichotomy(self, left, right):
delta = right - left
if delta < 1:
return left
if right ** 2 > self.x:
return self.dichotomy(left, (delta // 2) + left)
elif right ** 2 < self.x:
return self.dichotomy(right, right + delta)
else:
return right
def mySqrt(self, x):
self.x = x
half = (len(str(x)) // 2) + 1
return int(self.dichotomy(0, 10 ** half))
利用零點存在性定理，對 i^2 - x 的零點進行定位
其中 i 的范圍為0到10^(n/2)，n為x的位數
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/233580.html
標籤：其他