演算法筆記（九）：二分查找

（一）二分查找

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))