Поиск числа в монотонном увеличении и затем уменьшении последовательности
Поиск максимального или минимального значения в последовательности, которая увеличивается монотонно и затем монотонно уменьшается, может быть выполнено в 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
