Find a local minimum or peak with binary search

Given a non-empty integer array, return the index of a local minimum: an element no larger than its neighbours, where positions outside the array count as infinitely large. Use a left-biased binary search so the answer is deterministic, write it iteratively, and explain why the half you discard is safe. The same idea finds a peak.

Interface

Unless you agree on a different interface with the interviewer, assume:

• local_min(nums: list[int]) -> int — run the search on lo = 0, hi = n - 1; while lo < hi, compare nums[mid] with nums[mid + 1] and keep the left half when nums[mid] <= nums[mid + 1], otherwise the right half. Return lo.

Example

local_min([5, 3, 3, 4, 1, 2])  ->  1    # 3 <= 5 and 3 <= 3
local_min([9, 7, 7, 7, 8])     ->  1
local_min([1, 2, 3])           ->  0
local_min([3, 2, 1])           ->  2
local_min([4])                 ->  0

Constraints

• 1 <= len(nums) <= 10^5; values fit in 32-bit integers; duplicates allowed.
• O(log n) time, O(1) space.

Clarifying questions

• Strict or non-strict comparison with neighbours? (With duplicates, only the non-strict version always has an answer.)
• Is any local minimum fine, or a specific one?
• How do the ends compare?

What a strong answer covers

• The invariant: the left neighbour of lo is larger than nums[lo] (or lo = 0), and nums[hi] is no larger than its right neighbour (or hi = n - 1). Both survive each step, so when lo == hi that index is a local minimum.
• Why equality goes left: nums[mid] <= nums[mid + 1] keeps mid as a valid right end of the range.
• The peak version by flipping the comparison, and why both searches need no special handling at the ends.
• Tests: one element, two elements, plateaus of equal values, strictly monotone arrays.

Follow-ups

• Find a peak element instead.
• With duplicates and the strict definition, show an array where no local minimum exists and argue that no O(log n) method can work in general.
• A 2D version: find a cell no larger than its four neighbours.