title: Peak finding algorithm
body: <p>I recently started looking at MIT's 6.006 lectures and in the first lecture the instructor presented peak-finding algorithm.</p>
  
  <p><a href="http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/lecture-videos/MIT6_006F11_lec01.pdf" rel="noreferrer">http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/lecture-videos/MIT6_006F11_lec01.pdf</a></p>
  
  <p>According to his definitions:</p>
  
  <blockquote>
    <p>Given an array [a,b,c,d,e,f,g] where a-g are numbers, b is a peak
    if and only if a &lt;= b and b>= c.</p>
  </blockquote>
  
  <p>He gave a recursive approach:</p>
  
  <pre><code>if a[n/2] &lt; a[n/2 -1] then look for a peak from a[1] ... a[n/2 -1]
  else if a[n/2] &lt; a[n/2+1] then look for a peak from a[n/2+1] ... a[n]
  else a[n/2] is a peak
  </code></pre>
  
  <p>He said the algorithm is T(n) = T(n/2) + o(1) = o(lgn)</p>
  
  <p>In his pdf he also gave a complete example: <code>[6,7,4,3,2,1,4,5]</code></p>
  
  <p>Both 7 and 5 are peaks. But doesn't the algorithm above only finds 7 as peak just because the middle element happens to satisfy the first branch? </p>
  
  <ol>
  <li><p>So if we were supposed to find all the peaks, would we still be walking through the entire array? Would it mean worst case N?</p></li>
  <li><p>Does his definition implies we just need to find a single peak?</p></li>
  </ol>
  
  <p>I believe this problem can be viewed as finding the maximum and minimum element in Riverst's Introduction to Algorithm book. </p>