Нахождение любого локального минимума в массиве

Условие

Реализуйте функцию, принимающую массив уникальных чисел и возвращающую любой локальный минимум — элемент, который строго меньше своих соседних элементов.

def find_local_min(arr):
    # ваш код
    pass

Ответ

Принимая крайний элемент за локальный минимум, если он меньше единственного соседа, можно найти ответ бинарным поиском за O(log n).

def find_local_min(arr):
    if not arr:
        return None
    left, right = 0, len(arr) - 1
    while left < right:
        middle = (left + right) // 2
        if arr[middle] > arr[middle + 1]:
            left = middle + 1
        else:
            right = middle
    return arr[left]

Переходим в сторону убывания: там обязательно найдётся впадина либо минимальный край. Уникальность чисел исключает равные соседние значения. Единственный элемент подходит по принятому правилу границ.

Если локальным минимумом разрешено считать только элемент с двумя соседями, контракт другой: в монотонном массиве ответа нет. Тогда границы нельзя автоматически возвращать; простой линейный проход по внутренним индексам будет корректен.