title: Find the max and min of an increasing then decreasing list
body: <p>I've tried googling for this one without much success...I'm sure there's a technical name for this problem or for problems like it, but I can't seem to find the answer.</p>
  
  <p>Given a list <code>L</code> of integers, that is strictly increasing, and then strictly decreasing, find the maximum and minimum of that list.</p>
  
  <p>So for example, <code>L</code> might be <code>{1 2 3 4 5 4 3 2}</code> or <code>{2 4 5 7 3}</code>.  </p>
  
  <p>For finding the minimum, I said that the smallest integer had to either be the left or the right endpoint, so just compare the endpoints, and return the smallest one, giving constant time.</p>
  
  <p>For finding the maximum, I suggested basically a recursive binary search to find the point <code>L[x]</code> such that <code>L[x] &gt; L[x-1]</code> and <code>L[x] &gt; L[x+1]</code>, giving amortized lg(n) time.  He didn't seem to love that answer, and it does seem rather naive to me, so I'm wondering if there's something I'm missing.</p>
  
  <p>Thanks for the help!</p>
  
  <p>edit:</p>
  
  <p>My solution in python:</p>
  
  <pre><code>def Max(L):
      n = len(L)-1
      if n == 0:
          return L[0]
  
      if L[n/2] &gt; L[n/2 - 1] and L[n/2] &gt; L[n/2 + 1]:
          return L[n/2]
      elif L[n/2] &lt; L[n/2 + 1]:
          return Max(L[n/2:])
      else:
          return Max(L[:n/2])  
  </code></pre>