0

I saw the peak1d algorithm in here and on Peak finding algorithm.

I can't understand why it surely finds a peak if it exists. It seems that we are deciding to go with one half and can miss a peak on the other. I don't understand how comes you can apply a "binary search" technique for a random array (The array has no prior attribute).

How can I prove that if there is at least one peak inathe following algorithm will find one of the peak.

import random
a = [random.randint(0,100) for i in xrange(10)]

def peak1d(a,i,j):
    m = (i+j)/2
    if a[m-1] <= a[m] >= a[m+1]:
        return m
    elif a[m-1] > a[m]:
        return peak1d(a,i,m)
    elif a[m]<a[m+1]:
        return peak1d(a,m+1,j)


print a[peak1d(a,0,len(a))]
Community
  • 1
  • 1
0x90
  • 39,472
  • 36
  • 165
  • 245

1 Answers1

1

In case 1, a[m-1] <= a[m] >= a[m+1], we have a peak.

In case 2, a[m-1] > a[m], suppose we walk along the list, heading left. We may find higher and higher elements for a while, but eventually, one of two things will happen:

  1. We find an element less than or equal to the one we just looked at. Then the one we just passed is a peak.

  2. We hit the start of the list. Then the first element is a peak.

Thus, the first half of the list has a peak somewhere, and we can just look at that half. We don't need to consider the second half.

Case 3 is equivalent to case 2. We only need to consider the second half of the list, by the same reasoning.

Note that your implementation of the peak-finding algorithm is wrong. It doesn't handle the endpoints of the list correctly.

user2357112
  • 260,549
  • 28
  • 431
  • 505
  • In my implementation tail and head can't be a peak, a peak needs 2 neighbors. It still not clear to me why it is true, let's say this array `[17,...,17 , 15, 14 ,..., 28,29,27]` in the first iteration you will choose the left half, and you will miss the `29` peak. – 0x90 Apr 11 '14 at 05:43
  • @0x90: If a peak needs two neighbors, then this algorithm doesn't work. Take a closer look at the definition; peaks don't need two neighbors. (The SO post you linked skipped part of the definition; the PDF *it* links has the full definition.) As for your example, it doesn't matter whether we miss the 29 peak, because we'll find a 17 peak. If we tried the second half, we'd miss all those 17 peaks. We only need to find one peak. (Note that those 17s count as peaks.) – user2357112 Apr 11 '14 at 05:45
  • replace those 17 with `[100,99,98,97,..., 17, 15, 14 , ..., 28,29,27]`, the first iteration makes you to choose the left side but there is no peak there so the algorithm(as implemented in the pdf) can't find in O(log(n)) a peak, and might miss one – 0x90 Apr 11 '14 at 05:49
  • @0x90: 100 is a peak. Really, take a look at the definition of "peak" as given in the lecture slides. Both PDFs allow the endpoints to be peaks. – user2357112 Apr 11 '14 at 05:51
  • My main claim is, you can't look in part of a list, assuming there are no prior properties it holds. and you can't deduce you searched for all the array. – 0x90 Apr 11 '14 at 05:51
  • This algorithm is not guaranteed to find the highest peak, only *a* peak. Basically, it will find a local maximiser, which has the property that the elements on either side are smaller, not a global maximiser, which has the property that all other elements are smaller. – chthonicdaemon Apr 11 '14 at 05:53
  • You are since there is padding with minus infinity. in the video there is no padding [https://www.youtube.com/watch?v=HtSuA80QTyo] – 0x90 Apr 11 '14 at 05:53
  • @0x90: In the video, they define that an endpoint is a peak if its single neighbor is less than it. Take a look at 17:40. – user2357112 Apr 11 '14 at 05:56
  • @chthonicdaemon, I understand it finds a local maximum. the question why is there a case where there is a peak but the algorithm will announce there is no peak ? – 0x90 Apr 11 '14 at 07:13
  • @0x90: There is no such case. There is *always* a peak, and the algorithm will *always* find one. (Your implementation is broken, so your implementation won't necessarily find a peak, but a correct implementation will.) – user2357112 Apr 11 '14 at 07:16