Peak finding

Prerequisites

• Binary search: peak finding uses the same halving loop.
• Comparing an element with its neighbour.
• The idea of a "local" maximum versus the "global" maximum.

The analogy

How it works

Data requirement: none. Any array works, sorted or not. Treat positions outside the array as $-\infty$.

Start with one search by hand

Take [2, 5, 7, 8, 6, 3, 1], indices 0 to 6. At each step compare a[mid] with a[mid + 1]. Guess first, then open "Check".

Finish the picture

Peaks don't have to be the maximum. Try [1, 3, 2, 4, 6, 5], which has two peaks, 3 and 6.

• Step 1. mid = 2: compare 2 with 4. Predict the direction.
  Check

  2 < 4 is uphill to the right, so keep 3..5.

• Step 2. mid = 4: compare 6 with 5. Predict the peak returned.
  Check

  Downhill, so keep 3..4; then mid = 3, 4 < 6, keep 4..4. It returns 6, at index 4. The peak 3 at index 1 is never seen, and that's fine.

The rule in plain words

Look at the middle and its right neighbour. If the neighbour is bigger, the slope goes up to the right: keep the right part. Otherwise keep the middle and the left part.

When one element is left, it is a peak.

The code

Read this code after you have done one search by hand. It will make more sense.

int find_peak(const int a[], int n) {         /* returns the index of a peak */
    int lo = 0, hi = n - 1;
    while (lo < hi) {                          /* more than one candidate */
        int mid = lo + (hi - lo) / 2;          /* mid < hi, so mid + 1 is valid */
        if (a[mid] < a[mid + 1]) lo = mid + 1; /* uphill: peak on the right */
        else hi = mid;                         /* downhill: peak at mid or left */
    }
    return lo;
}

flowchart TD
  A["lo = 0, hi = n - 1"] --> B{"lo < hi ?"}
  B -->|no| C["Return lo: it is a peak"]
  B -->|yes| D["mid = middle of lo..hi"]
  D --> E{"a[mid] < a[mid+1] ?"}
  E -->|"yes: uphill"| F["lo = mid + 1"]
  E -->|"no: downhill"| G["hi = mid"]
  F --> B
  G --> B
          

How fast is it?

Each round halves the candidate range, and the loop runs until one element is left:

For our 7 elements, that's $\lceil \log_2 7 \rceil = 3$, exactly what we used.

Common mistakes

• Writing hi = mid - 1 on the downhill branch, which can throw away the peak at mid itself.
• Using lo <= hi: with hi = mid the range may stop shrinking, so the loop never ends.
• Thinking the answer is the largest element. It's only guaranteed to beat its neighbours.

Try it yourself

Did you know?

Key points to remember

If you remember one thing from each line, remember the because.

• A peak always exists because the maximum element is one, and rising values must end somewhere.
• The uphill half must contain a peak because walking up it either turns down or reaches the edge.
• It is $O(\log n)$ because each comparison halves the candidate range.
• It may miss the maximum because it only needs a local peak and ignores the other half.
• Extra space is $O(1)$ because it only keeps lo, hi and mid.

Self-check questions

Answer these in order, out loud. They follow the page, so your answers become the script of your video.

1. How is peak finding like hiking in fog?
   Sample answer

   You can only see the next step, so you always step uphill. That guarantees you reach some summit, though not necessarily the highest one.

2. Walk through peak finding on [2, 5, 7, 8, 6, 3, 1].
   Sample answer

   8 vs 6 is downhill, so keep 0..3; 5 vs 7 is uphill, so keep 2..3; 7 vs 8 is uphill, so keep 3..3. The peak is 8 at index 3.

3. Why does the code set hi = mid and not hi = mid - 1 on the downhill branch?

   A good answer says what mid might be.

   Sample answer

   When a[mid] ≥ a[mid+1], mid itself might be the peak. Excluding it could throw away the only peak in the range.

4. So what is peak finding, in one sentence?
   Sample answer

   It finds an element at least as big as its neighbours by repeatedly keeping the half on the uphill side of the middle.

5. Why must the uphill side contain a peak?

   A good answer follows the rising values to their end.

   Sample answer

   Walk uphill from mid + 1. Either the values stop rising at some point, which is a peak, or they keep rising to the edge, and the edge element is a peak because outside is $-\infty$.

6. What are its time and space complexity?
   Sample answer

   $O(\log n)$ comparisons in every case, since the loop always narrows to one element, and $O(1)$ extra space.

7. Why can't the same trick find the maximum in $O(\log n)$?
   Sample answer

   The maximum could be in the half we throw away, as in [9, 1, 2, 3, 4, 5, 0]. Only a local peak is guaranteed on the uphill side, so the maximum still needs $O(n)$.

8. If you had to teach this to a friend in 2 minutes, what would you leave out, and why?
   Sample answer

   I'd leave out the $-\infty$ boundary convention and the exact $\lceil \log_2 n \rceil$ count. I'd keep the fog analogy, the walk on the example, and "go uphill, halve each time, finds a peak, not the max".

External resources

• MIT OCW 6.006 Lecture 1: Algorithmic thinking, peak finding: the original lecture with notes.
• GeeksforGeeks: Find a peak element: linear and binary search versions with code.
• LeetCode 162: Find Peak Element: practise the exact problem.

Videos

• YouTube search: MIT 6.006 Lecture 1, peak finding: the full MIT lecture.