EdisonChendi
4/7/2018 - 11:45 AM

## mit6006_fall2011_lesson1

mit6006_fall2011_lesson1

``````#coding:UTF-8

from math import inf, floor
from time import time
from random import randint

def linear_find_peak_1d(l, start, end):
minus_inf = -1 * inf
l = [minus_inf] + l[start:end] + [minus_inf]
for i in range(1, len(l)+1):
if l[i] >= l[i-1] and l[i] >= l[i+1]:
return l[i], start+i-1
else:
raise Exception("no peak.")

def logarithmic_find_peak_1d(l, start, end):
if start == end:
return l[start], start

mid_idx = (end-start)//2 + start
mid = l[mid_idx]
mid_left = l[mid_idx-1]

try:
mid_right = l[mid_idx+1]
except IndexError:
mid_right = -1 * inf

if mid_left > mid:
return logarithmic_find_peak_1d(l, start, mid_idx)
elif mid_right > mid:
return logarithmic_find_peak_1d(l, mid_idx+1, end)
else:
return mid, mid_idx

n = 10
item_min = 1
item_max = 100
l = [randint(item_min, item_max) for i in range(n)]
print(l)
print(logarithmic_find_peak_1d(l, 0, len(l)))
print(linear_find_peak_1d(l, 0, len(l)))

###########################
# time complexity
# l = list(range(1,10000)) # worst case:

# def test(n, f, *args):
#     msg = "run {} on {} for {} time: {}"
#     start = time()
#     for i in range(n):
#         f(*args)
#     end = time()
#     print(msg.format(f.__name__, "range(1, 10000)", n, end-start))

# test(1000, linear_find_peak_1d, l, 0, len(l))
# test(1000, logarithmic_find_peak_1d, l, 0, len(l))

###########################
# ``````
``````#coding:UTF-8

from random import randint
from pprint import pprint
from math import inf

def logarithmic_find_peak_2d(arr, start, end):
print("=".center(40, "="))
print("start: {} end: {}".format(start, end))
if start == end:
col = arr[start]
return max(col), start, col.index(max(col))

mid_col_num = (end-start) // 2 + start
col_max = max(arr[mid_col_num])
col_max_idx = arr[mid_col_num].index(col_max)

col_max_left = arr[mid_col_num-1][col_max_idx]

try:
col_max_right = arr[mid_col_num+1][col_max_idx]
except IndexError:
col_max_right = -1 * inf

if col_max < col_max_left:
return logarithmic_find_peak_2d(arr, start, mid_col_num)
elif col_max < col_max_right:
return logarithmic_find_peak_2d(arr, mid_col_num+1, end)
else:
return col_max, mid_col_num, col_max_idx

def make_arr(n, m, min, max):
return [[randint(min, max) for j in range(n)] for i in range(m)]

def print_arr(arr, n, m):
for i in range(n):
for j in range(m):
print("%3d" % arr[j][i], end=" ")
print("")

n_row = 8
n_column = 8
item_min = 1
item_max = 100

arr = make_arr(n_row, n_column, item_min, item_max)
# pprint(arr)
print_arr(arr, n_row, n_column)
peak = logarithmic_find_peak_2d(arr, 0, n_column)
msg = "peak: {} col: {} row: {}"
print(msg.format(*peak))

``````