One Dimensional Peak Finding

Find an element that is at least as large as its immediate neighbors.

algorithmssearchingpeak-findingbinary-search

One Dimensional Peak Finding

One dimensional peak finding finds an index whose value is at least as large as its immediate neighbors. Unlike maximum search, it does not require finding the global maximum. Any local peak is enough.

For an array $A$, index $i$ is a peak if:

  • $i = 0$ and $A[0] \ge A[1]$
  • $i = n - 1$ and $A[n - 1] \ge A[n - 2]$
  • otherwise, $A[i] \ge A[i - 1]$ and $A[i] \ge A[i + 1]$

Problem

Given an array $A$ of length $n$, find an index $i$ such that $A[i]$ is a peak.

Assume out of bounds neighbors are treated as negative infinity:

$$ A[-1] = A[n] = -\infty $$

With this convention, every nonempty array has at least one peak.

Key Idea

Look at the middle index $m$.

If $A[m] < A[m + 1]$, then there must be a peak on the right side. Otherwise, there must be a peak at $m$ or on the left side.

This gives a binary-search-like algorithm, even though the array does not need to be sorted.

Algorithm

peak_finding_1d(A):
    l = 0
    r = length(A) - 1

    while l < r:
        m = l + (r - l) // 2

        if A[m] < A[m + 1]:
            l = m + 1
        else:
            r = m

    return l

Example

Let

$$ A = [1, 3, 4, 7, 6, 2] $$

The algorithm may return index $3$, because:

$$ A[3] = 7 $$

and

$$ 7 \ge 4,\quad 7 \ge 6 $$

So index $3$ is a peak.

Correctness

The algorithm maintains the invariant that the current interval contains at least one peak.

If $A[m] < A[m + 1]$, then the array rises from $m$ to $m + 1$. Moving right from $m + 1$, either values continue rising until the right boundary, or eventually stop rising. In both cases, there is a peak in $[m + 1, r]$.

If $A[m] \ge A[m + 1]$, then there is a peak in $[l, m]$ by the same argument in the left direction.

Each step keeps an interval containing a peak and strictly reduces its size. When $l = r$, the remaining index must be a peak.

Complexity

case time
all cases $O(\log n)$

Space:

$$ O(1) $$

method result time
maximum search global maximum $O(n)$
one dimensional peak finding any local peak $O(\log n)$

Peak finding is faster because it asks for a weaker result.

When to Use

Use one dimensional peak finding when:

  • any local optimum is acceptable
  • the array is not sorted
  • the data has hill-like or valley-like structure
  • logarithmic time is desired

Notes

  • The returned peak may not be unique.
  • The algorithm works with equal adjacent values.
  • For a strict peak, special handling is needed when duplicates occur.

Implementation

def peak_finding_1d(a):
    if not a:
        return -1

    l, r = 0, len(a) - 1

    while l < r:
        m = l + (r - l) // 2
        if a[m] < a[m + 1]:
            l = m + 1
        else:
            r = m

    return l

func PeakFinding1D(a []int) int {
    if len(a) == 0 {
        return -1
    }

    l, r := 0, len(a)-1

    for l < r {
        m := l + (r-l)/2
        if a[m] < a[m+1] {
            l = m + 1
        } else {
            r = m
        }
    }

    return l
}