小白的算法初识课堂(part1)--二分查找法
学习笔记
学习书目：《算法图解》- Aditya Bhargava
二分查找法
算法是一组完成任务的指令，任何代码片段都可视为算法。二分查找是一种算法，其输入是一个有序的元素列表（必须有序的原因稍后解释）。如果要查找的元素包含在列表中，二分查找返回其位置；否则返回null。
下面，我们玩一个猜数字游戏。我随便想一个1~100的数字，而你的目标是以最少的次数猜到这个数字。
简单查找
假设你从1开始依次往上猜，则每次猜测都只能排除一个数字，如果我想的数字是99，你得猜99次才能猜到！这是简单查找，更准确的说法是傻找。
二分查找法
假设你从50开始猜数字，下面是我们的对话：
#----第1轮----
你：猜50
我：小了
#----第2轮----
你：猜75
我：大了
#----第3轮----
你：猜63
我：大了
#----第4轮----
你：猜56
我：对啦！
我发现了，你每一次都猜余下数字的中间数字！比如，你猜50，我告诉你小了，你知道1 ～ 50都小了，所以就把1 ~ 50都排除，再选取56 ~ 100 的中间数字75，我又告诉你大了，你就把75~100排除，以此类推…
那么，你用的这种方法就是二分查找法。
一般而言，对于包含n个元素的列表，用二分查找法最多需要log2nlog_2 nlog2n步，运行时间为对数时间；而简单查找法最多则需要n步，运行时间为线性时间。
python实现
import math
def binary_search(my_list, item):
low = 0
high = len(my_list) - 1
while low item:
high = mid - 1
else:
low = mid + 1
return None
my_list = [2, 4, 6, 8, 10]
print(binary_search(my_list, 8))
控制台输出：
3
大O表示法
大O表示法是一种特殊的表示法，指出了算法的速度有多快。现在，我们用简单查找法和二分法来猜数字，假设一共有10，100，10,000和1,000,000,000个数字，查找一个元素要耗费1毫秒:
| 元素个数 | 简单查找 | 二分查找 | 倍数 |
|---|---|---|---|
| 10毫秒 | 10毫秒 | 4毫秒 | 2.5 |
| 100 | 100毫秒 | 7毫秒 | 14.29 |
| 10000 | 10000毫秒 | 14毫秒 | 714.29 |
| 1000000000 | 1000000000毫秒 | 30毫秒 | 33333333.33 |
我们看到，随着元素数量的增加，二分查找需要的额外时间并不多，而简单查找需要的额外时间却很多。因此，随着列表的增长，二分查找的速度比简单查找快得多。
因此，我们不能仅仅了解的算法运行时间，还需知道运行时间如何随列表增长而增加。这正是大O表示法的用武之地，大O表示法指出了算法有多快：
例如，假设列表包含n 个元素。简单查找需要检查每个元素，因此需要执行n 次操作，使用大O表示法，这个运行时间为O(n)；二分查找法则只需要执行log2nlog_2 nlog2n步，，使用大O表示法，这个运行时间为O(log2nlog_2 nlog2n)。需要注意的是，大O表示法指的运行时间并不以秒为单位，算法运行时间是从其增速的角度度量的。大O表示法让你能够比较操作数，它指出了算法运行时间的增速。
大O表示法指出了最糟情况下的运行时间
在从1~100猜数字游戏中，如果我设置被猜的数字为1，而你又用简单查找法从1开始猜数字，那岂不是1次就猜到了？那简单查找法的运行时间到底是O(n)还是O(1)呢？
简单查找法的运行时间总是O(n)，如果1次就找到了数字，那么将是最好的情形，但大O表示法说的是最差的情形。因此，你可以说，在最糟糕的情况下，简单查找法的运行时间是O(n)。这是一个保证，你知道简单查找的运行时间不可能超过O(n)。 说明除最糟情况下的运行时间外，我们还应该考虑平均情况的运行时间，这个知识点我们以后再说。
一些常见的大O运行时间
O(log n)，也叫对数时间，这样的算法包括二分查找。
O(n)，也叫线性时间，这样的算法包括简单查找。
O(n * log n)，这样的算法包括第4章将介绍的快速排序，一种速度较快的排序算法。
O(n2)，这样的算法包括第2章将介绍的选择排序，一种速度较慢的排序算法。
O(n!)，这样的算法包括接下来将介绍的旅行商问题的解决方案，一种非常慢的算法。
后记:还是想认认真真学学算法，一点点写吧.
山羊菌
原创文章 248获赞 452访问量 11万+
关注
私信
展开阅读全文
作者：山羊菌
