Peaking finding when equals is taken out of the equation I am going through the online course MIT OCW 6.006, lecture 1. It introduces a binary search algorithm that finds a peak in O(lgN) time.

A peak A[i] is defined as A[i]&gt;=A[i-1] and A[i]&gt;=A[i+1]. But I wonder what if the definition takes the equal sign out A[i]&gt;A[i-1] and A[i]&gt;A[i+1], a peak is defined as an element that is strictly larger than its neighbour.

Obviously, the binary search algorithm will not work without changes, because for a case that A[i]=A[i-1] and A[i]=A[i+1], it cannot decide to go left or right.

So, is there any algorithm that stills take O(lgN) time? (I personally think no, because for an array of equal numbers, aka the case that a peak does not even exists, you need to examine all elements)
I can further improve your approach - let's consider an array that has peak, but all but two elements in the array are equal. O(log n) comparisons can check only O(log n) elements, so it's not enough even to decide whether peak is in first or second half of the array.