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]>=A[i-1] and A[i]>=A[i+1]
. But I wonder what if the definition takes the equal sign out A[i]>A[i-1] and A[i]>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)