三个月算法进阶--day27
目录
提到数组没提非空，就应考虑空数组
设置哨兵
维护的值与更新答案
最优值，历史最低价格minprice
DP
dynamic programming; decision process
重叠子问题
动态规划，每一刻的状态都由之前的状态决定，dp状态机
n用来表示长度
无序表的顺序查找
有序表的二分查找
空列表与唯一元素列表可不作为特例，midpoint必须每次加减1
def binarySearch(alist, item):
found = False
start = 0
end = len(alist) - 1
while start <= end and not found:
midpoint = (end - start) // 2
if alist[midpoint] == item:
found = True
else:
if alist[midpoint] > item:
end = midpoint - 1
else:
start = midpoint + 1
return found
递归版本，切片的开销是为了可读性更好
def binarySearch(alist, item):
if len(alist) == 0:
return False
else:
midpoint = len(alist) // 2
if alist[midpoint] == item:
return True
else:
if item < alist[midpoint]:
return binarySearch(alist[:midpoint], item)
else:
return binarySearch(alist[midpoint+1:], item)
算法分析
基本计算步骤，足够简单，反复执行