1 二分查找
针对有序的元素列表
def binary_search(list,item):
low = 0
heigh = len(list)-1
while low <= heigh
middle = (low+height)//2
guess=list[middle]
if guess==item
return middle
if guess > item
height=middle-1
else
low=middle+1
return None
2 运行时
O(log n) 对数时间
O(n) 线性时间
O(n*log n) 对数线性
O(n^2) 指数
O(n!) 阶乘
3 数组和链表
数组 连续的内存空间存储类型相同的元素,但是新增元素需要重新申请空间,支持随机访问
链表 不一定是连续的空间,每一个都元素都包含下一个元素的地址,查找必须是从第一个开始,可以随意增删
4 递归
递归函数是自己调用自己的函数
每个递归函数必须都有两部分:基线条件(base case)和递归条件(recursive case)
