(一)二分查找
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))