二分查找
二分查找是一种算法,其输入是一个有序的元素列表。如果要查找的元素包含在列表中,二分查找返回其位置;否则返回 null 。
一般而言,对于包含n个元素的列表,用二分查找最多需要log2 n步,而简单查找最多需要n步。
仅当列表是有序的时候,二分查找才管用。
二分查找Python代码:
def binary_search(list,item): low = 0 high = len(list) - 1 while low <= high: mid = (low + high) // 2 guess = list[mid] if guess ==item: return mid if guess > item: high = mid - 1 else: low = mid +1 return Nonemy_list = [1,3,5,7,9]print (binary_search(my_list,3))print (binary_search(my_list,-1))
运行时间
最多需要猜测的次数与列表长度相同,这被称为线性时间(linear time)。
简单查找逐个地检查数字,如果列表包含100个数字,最多需要猜100次。如果列表包含40亿个数字,最多需要猜40亿次。二分查找则不同。如果列表包含100个元素,最多要猜7次;如果列表包含40亿个数字,最多需猜32次。二分查找的运行时间为对数时间(或log时间)。
大O表示法
大O表示法是一种特殊的表示法,指出了算法的速度有多快。
一些常见的大O运行时间
下面按从快到慢的顺序列出了你经常会遇到的5种大O运行时间。
- O(log n),也叫对数时间,这样的算法包括二分查找。
- O(n),也叫线性时间,这样的算法包括简单查找。
- O(n * log n),这样的算法包括第4章将介绍的快速排序——一种速度较快的排序算法。
- O(n2 ),这样的算法包括第2章将介绍的选择排序——一种速度较慢的排序算法。
- O(n!),这样的算法包括接下来将介绍的旅行商问题的解决方案——一种非常慢的算法。
小结
- 二分查找的速度比简单查找快得多。
- O(log n)比O(n)快。需要搜索的元素越多,前者比后者就快得越多。
- 算法运行时间并不以秒为单位。
- 算法运行时间是从其增速的角度度量的。
- 算法运行时间用大O表示法表示。