One-dimensional Peak finding problem

Definition

A peak in an array is a position that is greater than or equal to its adjacent elements. If the peak is an edge element — the first or the last element in the array — then it must be greater than or equal to its left-adjacent or right-adjacent element, respectively.

Problem: Find the peak in an array

So does a peak always exist?
Yes, it does, and there is a simple test for it. Start by thinking of all the different cases: when the elements are in increasing order, decreasing order, are all equal, and in random order.

Why ≧ and not simply >?
Think about the case when all elements are the same — a peak will never exist.

Brute-force algorithm

Start from the left and compare adjacent elements to each other until a peak is found.

n/2 elements on average
Worst-case time complexity: Θ(n)

Divide and conquer

There is a simple, yet efficient, approach to this problem: start looking from the middle.

For an array A[] of n elements,

1. if A[n/2 - 1] ≧ A[n/2], then look for the peak in the left half
2. if A[n/2 + 1] ≧ A[n/2], then look for the peak in the right half
3. Else, A[n/2] is the peak (trivial)

from typing import List

"""
Best-case: Θ(1)
Worst-case: T(n) = T(n/2) + Θ(1) = Θ(1) * (lg n) = Θ(lg n)
Average-case: Θ(lg n)
"""

def find_1d_peak(A: List[float], start: int, end: int) -> int:
    if start == end:
        return start
    mid: int = (start + end) // 2
    if A[mid-1] >= A[mid]:
        return find_1d_peak(A, start, mid-1)
    elif A[mid+1] >= A[mid]:
        return find_1d_peak(A, mid+1, end)
    else:
        return mid

Summary

That was a simple one-dimensional, peak-finding problem. I will look at the two-dimensional variant in the next post :)

Edit: Here is the second post