1

Разбираю на досуге курс Введение в алгоритмы от MIT

На первой лекции ожидал услышать о бинарном поиске и элементарных алгоритмах сортировки, но внезапно получил Peak Finder. Отправился гуглить => результат гуглёжки (на русском внятной инфы не нашёл): Годная статья хорошего человека

Идея ясна, но не могу понять, что происходит в коде в случае с одномерным массивом {1, 3, 4, 3, 5, 1, 3}

if a[n/2] < a[n/2 - 1] then only look at the left 1 ... n/2 - 1
else if a[n/2] < a[n/2 + 1] then only look at the right n/2 +1 ... n
else n/2 is a peak

Алгоритм для тех, кто не хочет переходить по ссылке на статью:

Необходимо найти пик(любой) в массиве. Пиковый элемент массива есть n, элемент слева от которого (a) и справа от которого (b) либо равен ему по значению, либо меньше его:

n - пик, если a ≤ n ≥ b

пиковые значения массивов

Берём значение в массиве и сравниваем с соседями. Если пик - отлично, программа завершена. Если нет - ищем дальше. Перемещаемся влево или вправо на одно число и снова сравниваем. отлично, программа завершена. Если нет - ищем дальше. Ну и так далее.

1 Вопрос: Пиков может быть несколько. Каким образом доработать алгоритм так, чтобы после нахождения пика программа продолжала работать, пока не найдёт все пики?

2 Вопрос: После первой итерации сравнения соседних значений программа должна переместиться влево или вправо по массиву. Указать ей явно, в какую сторону она должна двигаться как-то не логично, ведь после нахождения всех пиков слева ей нужно вернуться обратно и гулять направо. Как это сделать?

1 ответ 1

1

Идея ясна - похоже, не совсем.

Для быстрого поиска не перемещаемся на один элемент, а ищем в той половине, в которой точно должен быть пик (в правой, если правый элемент больше среднего). Это похоже на бинарный поиск и позволяет найти пик за логарифмической время. На каждом шаге интервал поиска сужается примерно вдвое.

Для поиска всех пиков достаточно линейного прохода по массиву, деление пополам здесь вроде ни к чему (например, в массив из всех одинаковых все элементы пики)

1
  • Да, действительно, как я найду всё пики в массиве, если буду что-то отсекать. Только перебор по сути 23 мая 2020 в 10:53

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.