Поиск числа в монотонном увеличении и затем уменьшении последовательности

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

Однако, если я хочу проверить, существует ли число в такой последовательности, это также можно сделать в O (log n)?

Я не думаю, что это возможно. Рассмотрим следующий пример: 1 4 5 6 7 10 8 3 2 0.

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

Я хотел бы знать, если этот поиск выполняется в O (log n) time?

Ответ 1

Как вы отметили, вы можете найти максимум (и его позицию) в O (logn). Затем вы можете просто выполнить двоичный поиск в каждой части, которая также является O (logn).

В приведенном выше примере вы найдете максимум 10 в позиции 5. Затем вы выполняете двоичный поиск в подпоследовательности [0..5] (1, 4, 5, 6, 7, 10). Поскольку 2 не найден, вы начинаете выполнять двоичный поиск в другой части (10, 8, 3, 2, 0).

Чтобы найти максимум в O (logn): посмотрите на два элемента по центру: 7 < 10. Итак, мы все еще находимся в возрастающей части и должны искать максимум в правой половине последовательности: (10, 8, 3, 2, 0). Посмотрите на 8 и 3, продолжите левую часть (10, 8).

Ответ 2

Как я помню, лучший поиск массивов, элементы которых упорядочены, увеличивается, а затем уменьшается, это алгоритм поиска Фибоначчи.

Ответ 3

Вот эскиз в python. Короче говоря, мы стремимся найти элемент, который граничит с возрастающей и убывающей областями (это мы проверяем двумя условиями, проверяющими соседние элементы). И мы продолжаем прыгать, как в стандартном бинарном поиске, пока не найдем этот элемент. Надеюсь, что это поможет.

def get_max(arr):
    if len(arr) == 1:
         return arr[0]
    if len(arr) in [0,2]:
        return None
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left+right) // 2
        #increasing region
        if arr[mid+1] >  arr[mid] and arr[mid] > arr[mid-1]:
            left = mid + 1
        #decreasing region
        elif arr[mid+1] < arr[mid] and arr[mid] < arr[mid-1]:
            right = mid - 1
        elif arr[mid+1] < arr[mid] and arr[mid-1] > arr[mid]:
            return arr[mid-1]
        else:
            return arr[mid]
    return -1