7.8 Peak Finding

Binary search is often associated with sorted data, but some of its most elegant applications work on arrays that are not sorted at all.

Peak finding is one such example.

A peak is an element that is greater than or equal to its neighbors. The array may rise and fall multiple times, contain local maxima, and have no global ordering. Despite this apparent lack of structure, a peak can still be located in logarithmic time.

The key insight is that binary search does not always require a sorted array. Sometimes it is enough to know which direction leads toward a solution.

This idea appears in optimization, signal processing, numerical analysis, machine learning, terrain modeling, and many divide-and-conquer algorithms.

Problem

Given an array, find any peak element.

For example:

[1, 3, 5, 4, 2]

The value:

is a peak because:

3 < 5 > 4

Another example:

[1, 2, 3, 1]

Peak:

And:

[1, 2, 1, 3, 5, 6, 4]

contains two peaks:

2
6

The problem requires finding any peak.

A linear scan is straightforward:

func FindPeakLinear(nums []int) int {
	for i := 0; i < len(nums); i++ {

		left := i == 0 ||
			nums[i] >= nums[i-1]

		right := i == len(nums)-1 ||
			nums[i] >= nums[i+1]

		if left && right {
			return i
		}
	}

	return -1
}

Time complexity:

O(n)

A logarithmic solution is possible.

Understanding Why a Peak Must Exist

Consider:

[1, 3, 5, 4, 2]

Starting from the left:

1 → 3 → 5

Values increase.

Eventually:

5 → 4

the trend reverses.

The turning point must be a peak.

Now consider:

[1, 2, 3, 4, 5]

The sequence never decreases.

The final element is therefore a peak.

Similarly:

[5, 4, 3, 2, 1]

The first element is a peak.

Every finite array contains at least one peak.

This guarantee makes binary search possible.

Key Observation

Suppose:

Index: 0 1 2 3 4
Value: 1 3 5 4 2

Midpoint:

      v
[1, 3, 5, 4, 2]

Compare:

nums[mid]
nums[mid+1]

If:

nums[mid] > nums[mid+1]

then a peak must exist on the left side, including the midpoint.

If:

nums[mid] < nums[mid+1]

then a peak must exist on the right side.

This observation allows us to discard half the search space.

Unlike ordinary binary search, we are not searching for a value. We are searching for a region that must contain a solution.

Solution

func FindPeak(nums []int) int {
	lo := 0
	hi := len(nums) - 1

	for lo < hi {
		mid := lo + (hi-lo)/2

		if nums[mid] > nums[mid+1] {
			hi = mid
		} else {
			lo = mid + 1
		}
	}

	return lo
}

Example:

nums := []int{1, 3, 5, 4, 2}

fmt.Println(FindPeak(nums))

Output:

Index 2 contains:

which is a peak.

Why Moving Left Works

Consider:

[1, 3, 5, 4, 2]

Suppose:

mid = 2

Then:

5 > 4

The sequence is descending.

Somewhere between the beginning and the midpoint there must be a peak.

Possibilities:

1 3 5 4 2
    ^

or:

1 4 3 2 1
  ^

Regardless of the exact shape, a peak exists in the left half.

Therefore:

hi = mid

is safe.

Why Moving Right Works

Now consider:

[1, 2, 3, 4, 5]

Midpoint:

Comparison:

3 < 4

The sequence is rising.

A peak must exist on the right.

Possibilities:

1 2 3 4 5
          ^

or:

1 2 3 4 7 6
          ^

As long as the slope rises, moving right cannot lose all peaks.

Therefore:

lo = mid + 1

is safe.

Example Walkthrough

Array:

[1, 2, 1, 3, 5, 6, 4]

Initial state:

lo = 0
hi = 6
mid = 3

Comparison:

3 < 5

Move right.

New interval:

[5, 6, 4]

Next iteration:

mid = 5

Comparison:

6 > 4

Move left.

Interval becomes:

[5, 6]

Next iteration:

6 > 5

Move left.

Search converges to:

Peak found.

Viewing the Array as a Landscape

A useful mental model is to imagine elevation.

1 3 5 4 2

becomes:

      *
    *   *
  *
*

At each midpoint, examine the slope.

If the terrain slopes upward, move uphill.

If the terrain slopes downward, move downhill.

A peak must exist in the chosen direction.

The algorithm follows gradients rather than exact values.

This intuition generalizes to many optimization problems.

Finding a Maximum in a Mountain Array

A mountain array increases and then decreases exactly once.

Example:

[1, 3, 6, 9, 7, 4, 2]

The peak:

is also the global maximum.

The same algorithm applies unchanged.

peak := FindPeak(nums)

For mountain arrays:

peak == maximum

This observation forms the basis of several optimization and search problems.

Infinite Search Spaces

The peak-finding principle extends beyond arrays.

Suppose a function increases and then decreases.

Example:

f(x)

with a single maximum.

The derivative changes sign:

positive → negative

The maximum acts as a peak.

Binary search can locate the transition.

Many numerical optimization methods build on this idea.

Comparing with Binary Search

Traditional binary search:

target < mid

or:

target > mid

Peak finding uses:

nums[mid] > nums[mid+1]

or:

nums[mid] < nums[mid+1]

The target value is irrelevant.

Only the direction of improvement matters.

This is an important conceptual shift.

The algorithm searches for structure rather than a specific element.

Complexity Analysis

Each iteration discards half of the remaining interval.

Time complexity:

Operation	Complexity
Peak finding	O(log n)

Space complexity:

Resource	Complexity
Extra memory	O(1)

No auxiliary data structures are required.

Common Mistakes

A common error is comparing both neighbors and attempting to determine whether the midpoint itself is already a peak.

That approach often complicates the logic unnecessarily.

The simpler strategy compares only:

nums[mid]
nums[mid+1]

and follows the slope.

Another mistake is using:

mid - 1

without verifying bounds.

The standard formulation avoids this issue entirely.

A third mistake is assuming the algorithm finds the highest peak. It does not.

The algorithm guarantees finding a peak, not necessarily the global maximum.

For mountain arrays those concepts coincide, but for arbitrary arrays they may differ.

Takeaway

Peak finding demonstrates that binary search is fundamentally a divide-and-conquer strategy rather than a search technique for sorted arrays. By examining the local slope around the midpoint, the algorithm determines which half must contain a peak and discards the other half. The result is a logarithmic-time solution for a problem that appears unsorted and irregular. This technique forms the foundation for mountain-array searches, unimodal optimization, gradient-based reasoning, and many advanced divide-and-conquer algorithms.