Разбираю на досуге курс Введение в алгоритмы от 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 Вопрос: После первой итерации сравнения соседних значений программа должна переместиться влево или вправо по массиву. Указать ей явно, в какую сторону она должна двигаться как-то не логично, ведь после нахождения всех пиков слева ей нужно вернуться обратно и гулять направо. Как это сделать?