Peak Finding Problem

peakfinding.py

''' Peak Finder 1-D version.
Runs on an array of numbers
Task : Find a *peak* (IF IT EXISTS) 
Peak iff b>=a , b>=c ( equal or greater than Right , Left elts)
If corner elements then equal or greater to whatever R/L
'''

'''Algo (straightforward):
Start from left
n/2 might be the peak //*\\ ( look at n/2 elts )
worst case : theta(n) look at all n elts
gives both lower and upper bound
big oh- upper bound
'''

'''Better algo (DnC) (Binary search)
look at n/2 position
if a[n/2] < a[n/2 - 1] 
  then only look at left half 1...n/2 -1 for a peak
else if a[n/2]<a[n/2+1]
  then only look at right half n/2 +1...n for a peak
else
  n/2 is a peak
'''

'''Complexity of BST
T(n) "work" algo does on input of size n
T(n) = T(n/2) + theta(1)
base case : T(1) = theta(1)
T(n) = theta(1)+ ... theta(1) 
log2 n times

>====theta(log2 n)<======

'''

'''2D Version
n rows * m columns
Greedy Ascent Algorithm
worst case : theta(nm) complexity
*** Incorrect version ***
- Pick middle column j = m/2
- Find a 1D peak at (i,j) ( theta(log2 n) )
- Use (i,j) as a start to find a 1D peak on row i ( theta(log2 m) )
Problem is a 2D peak may not exist on row i.
*** Correct Version ***
Recursive Version
- Pick a middle column j= m/2
- Find a global maxima on col j (i,j)
- Compare i,j-1 ; i,j ; i,j+1
- Pick left column if i,j-1 > i,j
or 
- Pick right column if i,j+1 >i,j

if i,j >= i,j+1 and i,j-1
==>> i,j is a 2d peak
Solve the new problem with half the number of columns
When you have a single column , find the global maximum. That's it (base case)
Complexity : 
T(n,m) = T(n,m/2) + theta(n)
T(n,1)=theta(n)
>======== T(n,m) = theta(n log2 m) <=======
'''