（一）二分查找
1、例如：抱著一堆書走出圖書館的時候，檢測器突然響了（其中一本書沒有消磁），現在要檢查哪一本書沒有消磁，
（1）比較耗時的方式就是，一本一本書用檢測器都檢查下，
（2）比較快的方式是：分成相等的2份，分別給檢測器檢測，引起報警的那一份，再分成2份，分別給檢測器檢測，重復這個程序，直到找到引起報警的那本書，
第二種方式就體現了二分查找思想，
2、二分查找依賴的是順序表結構，簡單的說就是陣列，（二分查找需要按照下標隨機訪問元素，用其他資料結構，例如鏈表的話，時間復雜度會變高）
3、二分查找針對的是有序資料，
4、資料量太小不適合二分查找（因為此時遍歷、二分查找花的時間差不多）
5、資料量太大也不適合二分查找，（二分查找底層依賴陣列這種資料結構，而陣列需要連續的記憶體空間，如果資料量太大，太耗記憶體，）
6、二分查找的時間復雜度為O（logn）
（二）練習題
1、實作“求一個數的平方根”，精確到小數點后 6 位，
1 def mySqrt(n): 2 l = 0 3 r = n + 1 4 while l < r: 5 mid = l + (r - l) // 2 6 if mid ** 2 == n: 7 return "{}.000000".format(mid) 8 elif mid ** 2 < n: 9 l = mid + 1 10 elif mid ** 2 > n: 11 r = mid 12 inte = l -1 # 開方整數部分 13 result = inte + 0.5 # 該行及下面的for回圈根據開方公式計算小數部分 14 for i in range(1,7): 15 result = result + (n/result - result)*0.5 16 result = str(result).split(".") 17 result = float("{}.{}".format(result[0],result[1][:i])) # 保留小數位，根據開方計算公式，依次保留1、2、3...位小數 18 return result 19 20 print(mySqrt(5))
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/145090.html
標籤：Python
上一篇：微信機器人之PC微信hook