Нахождение числа в монтонически возрастающей, а затем убывающей последовательностиcera

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

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

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

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

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


c algorithm binary-search
person vamsi    schedule 18.07.2012    source источник

Ответы (3)


arrow_upward
12
arrow_downward

Как вы заметили, вы можете найти максимум (и его положение) в 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).

person Henrik    schedule 18.07.2012
comment
Не могли бы вы продолжить приведенный выше пример, найдя 2 в приведенной выше последовательности. и получить решение за O(logn) - person vamsi; 18.07.2012
comment
Хм... проблема здесь в том, чтобы найти максимум в O (logn). Остальное, как вы сказали - person Andy Stow Away; 18.07.2012
comment
@AndyStowAway Я думал, что это ясно (для ОП). Отредактировал мой ответ. - person Henrik; 18.07.2012
comment
Обратите внимание, что последовательность монотонна. Так что могут быть дубликаты. Таким образом, найти максимум с вашей логикой не получится. - person Prakash Kuma; 30.08.2016

arrow_upward
0
arrow_downward

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

person Hovo    schedule 20.04.2017

arrow_upward
0
arrow_downward

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

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
person Egor Lakomkin    schedule 29.01.2018