Introduction

A local minimum in an array is an element that is no larger than its neighbors. This is a useful primitive in optimization, signal processing, and interview problems because you often do not need the global minimum; you only need one position where the values stop decreasing locally.

What Counts as a Local Minimum

For an array a:

• index 0 is a local minimum if a[0] <= a[1]
• index n - 1 is a local minimum if a[n - 1] <= a[n - 2]
• any middle index i is a local minimum if a[i] <= a[i - 1] and a[i] <= a[i + 1]

In the array 9, 7, 2, 8, 5, both 2 and 5 are local minima. That example already shows why the problem is usually framed as "find a local minimum" rather than "find the local minimum." There may be several valid answers.

Linear Scan

The simplest solution is to check each element against its neighbors until you find one that satisfies the rule.

1def find_local_min_linear(values):
2    if not values:
3        raise ValueError("array must not be empty")
4
5    n = len(values)
6    if n == 1 or values[0] <= values[1]:
7        return 0
8
9    for i in range(1, n - 1):
10        if values[i] <= values[i - 1] and values[i] <= values[i + 1]:
11            return i
12
13    return n - 1
14
15
16data = [9, 7, 2, 8, 5]
17idx = find_local_min_linear(data)
18print(idx, data[idx])

This runs in O(n) time and is perfectly acceptable unless the array is very large or the problem explicitly asks for something faster.

Binary Search for O(log n)

A more interesting result is that you can find one local minimum in logarithmic time. The key observation is:

• if the middle element is already a local minimum, return it
• if the left neighbor is smaller, there must be a local minimum somewhere on the left
• otherwise there must be a local minimum somewhere on the right

Why does that work? If you keep moving from a value to a smaller neighbor, you cannot descend forever without either reaching the boundary or reaching a point where the descent stops. That stopping point is a local minimum.

Here is an iterative implementation:

1def find_local_min_binary(values):
2    if not values:
3        raise ValueError("array must not be empty")
4
5    left = 0
6    right = len(values) - 1
7
8    while left <= right:
9        mid = (left + right) // 2
10
11        left_ok = mid == 0 or values[mid] <= values[mid - 1]
12        right_ok = mid == len(values) - 1 or values[mid] <= values[mid + 1]
13
14        if left_ok and right_ok:
15            return mid
16
17        if mid > 0 and values[mid - 1] < values[mid]:
18            right = mid - 1
19        else:
20            left = mid + 1
21
22    raise RuntimeError("unreachable")
23
24
25data = [10, 6, 7, 3, 4, 8]
26idx = find_local_min_binary(data)
27print(idx, data[idx])

The code returns an index, which is usually more useful than returning the value alone.

Why the Binary Approach Is Valid

Suppose values[mid - 1] < values[mid]. Moving left starts on a downward slope. Either that slope eventually bottoms out inside the left half, or it keeps descending until it reaches the left boundary. In either case, a local minimum exists there.

The symmetric argument holds on the right side. This is what makes the divide-and-conquer method correct even though the array is not sorted.

That point often surprises people. Binary search is usually associated with sorted data, but the deeper requirement is stronger structure, not necessarily sorting. Here the structure is the guarantee that a downward direction leads to some local minimum.

Common Pitfalls

Boundary handling is the most common bug. The first and last elements only have one neighbor, so they must be treated separately or folded into the logic with careful checks.

Duplicates also matter. If the problem defines a local minimum using strict inequality, then plateaus behave differently. The implementations above use <=, which treats flat regions as valid local minima.

Another mistake is returning the value instead of the index when the caller needs the position. Decide that interface up front.

Finally, do not confuse a local minimum with the global minimum. A binary-search solution can return any valid local minimum, not necessarily the smallest number in the entire array.

Summary

• A local minimum is an element no larger than its neighbors.
• A linear scan finds one in O(n) time and is easy to implement.
• A modified binary search finds one in O(log n) time.
• The binary method works because moving toward a smaller neighbor must eventually lead to a local minimum.
• Pay close attention to boundaries, duplicates, and whether the caller needs an index or a value.