# 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]>=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)

• Do you need to examine all the elements just because there's no peak? With the "official" definition of peak, a list of strictly increasing numbers has no peak but the standard algorithm still runs in $O(\lg N)$ time, right? – David Richerby Aug 20 '18 at 17:21
• @DavidRicherby But without examining all elements, you cannot make sure there is no peak. Maybe just the elements you did not examine are not peak. – Levin Kwong Aug 20 '18 at 17:29
• I'm confused. You claim that there is an algorithm that finds peaks in logarithmic time. What happens when that algorithm is run on an input with no peaks (e.g., a list of strictly increasing numbers)? Does it still run in logarithmic time then? – David Richerby Aug 20 '18 at 17:51

• I think the key is the index i of the current step of binary search, if A[i]=A[i-1] and A[i]=A[i+1]. If only 2 elements are equal, let say A[i]=A[i-1] then we still can have an algorithm that if A[i]<A[i+1], go right; if A[i]>A[i+1], go left – Levin Kwong Aug 20 '18 at 17:14