Two peaks finding algorithm We are given an array of length N with exactly 2 peaks (a peak is an element which is no less than the left and right neighbors). Is there an algorithm to compute those peaks faster than O(N), maybe similar with the single peak finding in O(log N)?
No. Any algorithm to locate those two peaks will take $\Omega(N)$ time, assuming that the only operation allowed is to compare two elements in the array, i.e., the comparison mode.

Otherwise, suppose algorithm $A$ do not need that much time. Let $arr[0], arr[1], \cdots, arr[N-1]$ be the given array. Then for some $N$ large enough, $A$ will have only checked at most $N-3$ elements before it has terminated. Suppose for all comparisons that have done by $A$, it will be found that $arr[i] &lt; arr[j]$ where $i&lt;j$.

Let $arr[a], arr[b], arr[c]$ be three elements that have not been checked yet, $a&lt;b&lt;c$. Whatever $A$ have done, the two peaks could be $\{arr[a], arr[N-1]\}$. They can be $\{arr[b], arr[N-1]\}$ as well. Since $A$ cannot distinguish these two cases, $A$ cannot possibly have determined the two peaks.

Exercise. (less than one minute) Modify the above argument so that it becomes valid in the case when a peak must have both left neighbor and right neighbor.