目录
二分查找
假设要在字典中查找一个以o开头的单词，可以从头开始查找，直到进入以o开头的部分。但是你很有可能不这样做，而是从中间附近开始查找，因为你知道o在中间附近，明显也更合逻辑。
这是一个查找问题，可以使用算法二分查找来解决问题。
工作原理
我随便想一个1~100的数字，你的目标是以最少的次数猜中这个数字，你每次猜测后，我会说：小了，大了，或者对了。假若你从1开始猜，那你只能排除一个数字。
最佳的查找方法：
从50开始查找，小了或者大了都能排除一半的数字。假若50小了，那就再来75。不断的排除一半的数字，最终得到答案。
这就是二分查找，
100--->50--->25--->13--->7--->4--->2--->1
七步就能够从100个数字内排除到最后的正确答案。
说明：
仅当列表或者数据是有序排列时，二分查找才有效。
那么我们来运行python来试试二分查找：
首先我们要查找的部分是从low到high；函数binary_search接受参数为一个有序数组和一个被查找的元素。
low = 0 high = len(list1)-1
我每次都要检查中间的元素：
mid = (low + high) // 2 guess = list1[mid]
如果数字猜小了， 就相应的修改low：
if guess < item: low = mid + 1
如果大了，就修改high。
完整的代码如下：
def binary_search(list1, item): low = 0 high = len(list1)-1 # low 和 high用于跟踪要在其中查找的列表部分 while low <= high: # 只要范围没有缩小到只包含一个元素 mid = (low + high) // 2 # 就检查中间的元素 guess = list1[mid] if guess == item: # 找到了元素 return mid if guess > item: # 数字猜大了 high = mid - 1 else: low = mid + 1 # 数字猜小了 return None # 没有指定的元素 my_list = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19] # 测试例子 print(binary_search(my_list, 3)) # 索引从0开始，第二个位置的索引为1 print(binary_search(my_list, 17))
运行时间
说到算法，就离不开他的。运行时间。一般而言，应选择效率最高的算法，以最大限度的减少运行时间或占用的空间。
简单查找逐个的检查数字，如果列表包含100个数字，最多需要猜100次。换言之，最多需要猜测的次数与列表长度相同，这被称为线性时间（linear time）。
简单查找的运行时间为：O（n）线性时间
二分查找的运行时间为：O（log n）对数时间
在下面会又更多的运行时间。
大O表示法（表示算法的速度）·····
大O表示法指出了算法有多快的一种特殊表示法（运算运行时间的增速），定义为数量越多时算法运行时间的增速，增速越慢，代表算法越快。
知道算的快有什么用呢？？？其实蛮重要的哈，实际上，我们会经常用到别人编写的算法，在这种情况之下，知道这些算法的的速度就大有脾益。
注意
- 大O表示法指的并非以秒为单位的速度
- 大O表示法所表示的是一个算法在最糟糕情况下的运行时间（简单来理解就是运行所需要的最长的时间）
常见的大O运行时间：
是有点多的
- O(1)：是最低的时间复杂度，表示算法的速度和数量无关，不论数量是多少，算法的速度始终不变，也就是耗时/耗空间与输入数据大小无关，无论输入数据增大多少倍，耗时/耗空间都不变
- O(n)：也叫线性时间，表示算法的速度和数量增加呈现线性增长
- O(log n)：也叫对数时间，是一种随着数量越多，算法耗时增速越慢的算法
- O(n * log n):是一种速度较快的排序法
- O(n²)：一种速度较慢的排序法
- O(n!): 是一种非常慢的算法
注意：
大O比较的是操作数，它指出了算法运行时间的增速，括号里的是操作数
主要理解
- 用大O表示法表示算法的运行时间
- 算法的速度指的是操作数的增速，而非时间
- 谈论算法速度说的是随着输入数据的增加，其运行时间将以什么样的速度增加
哈哈哈哈哈为什么叫大O表示法，是因为操作数前有个大O。哈哈哈哈哈哈哈哈哈哈哈哈哈
