title: Local minimum in unsorted array
body: <p>Suppose I have an array a[i] for 0&lt;=i&lt;=n-1. Can I find, using an algorithm of complexity O(log n), i such that 1&lt;=i&lt;=n-2, a[i]&lt;=a[i+1] and a[i]&lt;=a[i-1]? That is, can I find a local minima in logarithmic time?</p>
  
  <p><sub><strong>Note</strong>: I edited the question (which had changed many times) to be one that could reasonably be answered. I removed the strange end conditions that appeared in an earlier version because this version is simpler and yet loses no generality.</sub></p>