（一）二分查找

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