MIT6.006是Algo Intro这门课，据说语言使用python
Lec01是讲peak finding，也就是峰值点
具体为：
一维情况下一个数组中a[i]>a[i-1]且a[i]>a[i+1]那么它是peak 边界时检查一个方向就ok
二维情况下需要某元素x比四个相邻元素都大，边界也类似一维去处理
只要找到一个peak返回就好
复杂度：
一维用二分，log n
二维先二分，二分后的一维数组遍历一下，所以是O(n*log n)
代码：
# coding:utf8
# MIT6.006 Lec01
# peakfinder in 1D condition
# --by HaxtraZ
def peakfinder(a):
# a is a list. you can also treat it as an array
n = len(a)/2
while True:
if n!=0 and n!=len(a):
if a[n/2] < a[n/2-1]:
#look at left half
peakfinder(a[:n/2])
elif a[n/2] < a[n/2+1]:
#look at right half
peakfinder(a[n/2+1:])
else:
return a[n/2]
elif n == 0:
if a[0]>a[1]:return a[0]
else:return a[1]
elif n == len(a):
if a[n]>a[n-1]:return a[n]
else:return a[n-1]
# coding:utf8
# MIT 6.001 Lec1
# peakfinder in 2D condition
# ----by HaxtraZ
def globalMaxIndex(b):
# you can assum b is a 1-D array
key = 0
val = b[0]
blen = len(b)
for j in (1,blen):
if b[j] > val:
key = j
val = b[j]
return key
def peakFinder(a):
# a is a 2D-list 二维方格
j = len(a)/2
i = globalMaxIndex(a[j])
# get the global max value in the j-th line
if j!=0 and j!=len(a):
if a[j-1][i] > a[j][i]:
# 检查上半部分
return peakFinder(a[:j])
elif a[j+1][i] > a[j][i]:
# 检查下半部分
return peakFinder(a[j+1:])
else:
return a[j][i]
elif j==0:
if a[0][i]>a[1][i]:return a[0][i]
else:return a[1][i]
elif j==len(a):
if a[n-1][i]>a[n][i]:return a[n-1][i]
else:return a[n][i]
Lec01的pdf课件在这里
