LeetCode 162 · Binary search

Find Peak Element, explained with a picture

A hiker who always walks uphill.

Binary search
▶ Watch it step by step

The problem

Find any peak: a position whose value is bigger than both neighbours (outside the list counts as −∞).

Input:  [1, 2, 1, 3, 5, 6, 4]
Output: 5   (value 6; position 1 is also a peak)

Picture it

Picture a hiker in fog who can only see neighbouring spots. If the trail goes uphill to the right, keep walking right: you must hit a summit eventually. Binary search does this by checking the middle and moving towards the uphill side.

Short version: the full lesson (brute force, complexity, edge cases and a quiz) is still being written. The animation is complete.

The key idea

If nums[mid] < nums[mid + 1], a peak lies to the right; otherwise to the left (or at mid). O(log n).

Python solution

def find_peak(h):
    lo, hi = 0, len(h) - 1
    while lo < hi:
        mid = (lo + hi) // 2
        if h[mid] < h[mid + 1]:
            lo = mid + 1          # uphill to the right
        else:
            hi = mid              # a peak is at mid or left
    return lo

In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.