二分查找和大O表示法
第一章 算法简介
一、第一种查找算法-----二分查找
二、算法的运行时间-----大O表示法
一、二分查找
例子：
随便想一个1-100的数字，例如57，目标是以最少的次数猜到这个数字，每一次猜测之后会说小了，大了，或者对了。
假设从1开始猜，那么猜测过程是这样的：
这种方法每一次只猜一个数字，如果想的数字是1，那么只需要猜一次就可以猜中，如果想的数字是100，则需要猜100才可以猜中，很浪费时间。
现在提出一种新的方式，可以更高效的找到猜想的数字。这种查找方式是----二分查找。
二分查找的方法如下：
①猜想的数字是0-100，那么先从0-100的中间数 50 开始，则会有如下结论：50虽然小了，但是我们排除了0-50的数字。
②从50-100的中间数 75 猜，会有如下结论：75大了，但我们可以排除75-100的数字。
③从50-75的中间数 63 猜，会有如下结论：63大了，排除63-75的数字。
④从50-63的中间数 57 猜，得到结论：57对了
这就是二分查找的全过程。
代码实现：
编写执行二分查找的python代码，代码示例使用数组（在python中叫做列表）
tips：1、给出的序列必须有序，才可以进行二分查找
2、在python3中，/表示浮点数除法，//表示整数除法
设置二分查找函数：binary_search，如果指定的元素包含在数组中，这个函数将返回其位置。
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 None
my_list = [1,3,5,7,9]
print(binary_search(my_list,3)) # 输出为1 下标为1 找了两次
print(binary_search(my_list,-1)) # 输出为None 找不到
二、大O表示法
刚刚学习了二分查找，可以看到使用二分查找对0-100的数字57进行查找时，需要的次数是4次，但是如果最开始的数字是1，那要找7次，每一次都是对半查找，所以时间为logn。
对于简单查找来说，n的元素，最少查找一次，最多查找n次，平均查找时间是(n+1)/2。
大O表示法是一种特殊的表示法，指出算法的速度有多快，可以使用它列出一些最常用的算法运行时间。
例如简单查找的运行时间为O(n)，二分查找的运行时间为O(logn)。
大O表示法指出了最糟糕情况下的运行时间。
一些常见的大O运行时间：
O(logn)：对数时间，例：二分查找等
O(n)：线性时间，例：简单查找等
O(n*logn)：例：快速排序----一种速度较快的排序算法
O(n^2)：选择排序----一种速度较慢的排序算法
O(n!)：旅行商问题----一种非常慢的算法
运行时间排序：O(logn)<O(n)<O(n*logn)<O(n^2)<O(n!)
三、小结
1、二分查找的速度比简单查找快得多。
2、O(logn)比O(n)快，需要搜索的元素越多，前者比后者就快得多。
3、算法运行时间并不以秒为单位。
4、算法运行时间是从其增速的角度度量的。
5、算法运行时间用大O表示法表示。
6、大O表示法表示的是算法最坏情况下的运行时间。