1
$\begingroup$

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)

|cite|improve this question
$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – David Richerby Aug 20 '18 at 17:21
  • $\begingroup$ @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. $\endgroup$ – Levin Kwong Aug 20 '18 at 17:29
  • $\begingroup$ 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? $\endgroup$ – David Richerby Aug 20 '18 at 17:51
1
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – Levin Kwong Aug 20 '18 at 17:14
  • $\begingroup$ But if all examined points have A[i-1]=A[i]=A[i+1], we will have no idea where to go, and can't find a peak among the remaining (not checked) array elements. $\endgroup$ – Bulat Aug 20 '18 at 18:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.