Представьте себе массив чисел, в котором существует только одна вершина, как найти такое число и его индекс? Последовательный поиск, вероятно, первое решение, которое приходит нам в голову. Можем ли мы сделать лучше? Да, вероятно, используя двоичный поиск, чтобы уменьшить временную сложность с O(N) до log(N). Это единственное решение, которое у нас есть? НЕТ… мы могли бы использовать более продвинутый и утонченный подход под названием Поиск золотого сечения.

Вопросы:
Назовем массив A горой, если выполняются следующие свойства:

  • A.length >= 3
  • Есть такие 0 < i < A.length - 1, что A[0] < A[1] < ... A[i-1] < A[i] > A[i+1] > ... > A[A.length - 1]

Для массива, который определенно является горой, верните любое i такое, что A[0] < A[1] < ... A[i-1] < A[i] > A[i+1] > ... > A[A.length - 1]

Решения:
Давайте сначала рассмотрим закуски, прежде чем переходить к главному блюду.

  • # 1) Стандартный метод линейного / последовательного поиска, найдите индекс пика i, где A[i]>A[i+1]. O(N) временная сложность, очень прямолинейно.
  • # 2) Двоичный поиск, определение указателей left и right и вычисление mid для каждой итерации. Когда A[mid]<A[mid+1], это означает, что числа все еще увеличиваются, поэтому пик должен находиться справа от mid, поэтому мы обновляем указатель left; В противном случае это означает, что пик должен быть слева от mid, мы обновляем указатель right. В конце концов, встречаются два указателя и определяется пиковый индекс. Olog(N) временная сложность, намного быстрее, если у нас большой ввод.
  • №3) Поиск по золотому сечению - это метод нахождения минимума / максимума строго унимодальной функции (идеально соответствует нашему определению проблемы горы с единственной вершиной). Чтобы понять алгоритм, нам нужно вспомнить золотое сечение ϕ (phi) и вывести некоторые из его свойств, которые будут использоваться позже.

(a+b)/a = a/b = ϕ
1 + 1/ϕ = ϕ
ϕ^2 - ϕ - 1 = 0
Solve for ϕ and given ϕ > 0:
ϕ = (1+sqrt(5))/2 = 1.61803...
From 1 + 1/ϕ = ϕ, we get 1/ϕ = ϕ - 1, divided both sides by ϕ:
1/(ϕ^2) = 1 - 1/ϕ

Теперь давайте разберемся, как работает поиск по золотому сечению, с помощью приведенного ниже графика. Задача - найти максимальное значение (пик). Учитывая left и right границы исходного пространства поиска, мы хотели бы сначала найти две золотые точки x1 и x2, где (x2-left)=(right-x1) и (right-left)/(x2-left) = (x2-left)/(x1-left). Это именно тот вывод, который мы сделали ранее. Следовательно, мы формулируем x1 и x2 как:

x1 = right - (right-left)/ϕ
x2 = left + (right-left)/ϕ

Далее мы собираемся сравнить значения f(x1) и f(x2). Подобно двоичному поиску, пространство поиска уменьшается после каждой итерации. Если f(x1)>f(x2), мы понимаем, что пик не может находиться между x2 и right, поэтому мы сокращаем диапазон поиска и обновляем right до значения x2.

после определения нового right нам нужно пересчитать x1 и x2. Есть уловка для сохранения вычислений относительно newx2 (как x2' ниже).

x2' = left + (right'-left)/ϕ,  where right' = x2 = left + (right-left)/ϕ
substitute right' and with some algebra, we get:
x2' = left + (right-left)/(ϕ^2), 
Recall earlier we proved 1/(ϕ^2) = 1 - 1/ϕ, again with some algebra:
x2' = right - (right-left)/ϕ = x1
Amazing! x2' = x1

Здесь мы показали, что новое значение x2 будет просто значением x1 в предыдущей итерации. Это одно из удивительных свойств золотого сечения ϕ (фи). Точно так же, если f(x1) < f(x2), мы понимаем, что пик не может находиться между left и x1, поэтому мы обновляем left до значения x1 (left=x1) и нового x1, чтобы он был значением x2 в предыдущей итерации.

Собрав все части вместе, у нас есть код ниже. Применено несколько методов оптимизации кода: 1) Умножение работает лучше, чем деление, поэтому вместо применения деления на phi мы умножаем его обратное phi_inv. 2) Вернемся к исходной проблеме Mountain Array, функция f на самом деле является дискретной унимодальной функцией, которая преобразует целочисленные индексы в целые значения. Следовательно, в служебных функциях cal_x1 и cal_x2 должно применяться целочисленное округление. После того, как поиск сходится, требуется некоторая пост-проверка и корректировка, чтобы убедиться, что введен правильный индекс.

Алгоритм можно дополнительно усовершенствовать с помощью интересного математического вывода, касающегося вычисления нового x1 после оператора x2=x1. Здесь я докажу x1' = cal_x1(left,right') = cal_x2(left, x2'). Обратите внимание, здесь x2' уже был обновлен до значения x1 в предыдущей итерации.

Apply formula for calcualting x1:
x1' = cal_x1(left,right') = right' - (right'-left)/ϕ = x2 - (x2-left)/ϕ
Recall x2 = left + (right-left)/ϕ, substitute x2 in the above equation & with some algebra
x1' = left + (ϕ-1)(right-left)/(ϕ^2)
What about cal_x2(left,x2')?
cal_x2(left,x2') = cal_x2(left,x1) = left + (x1-left)/ϕ
Recall x1 = right - (right-left)/ϕ, substitute x1 in the above equation & with some algebra
cal_x2(left,x2') = left + (ϕ-1)(right-left)/(ϕ^2)
Amazing! x1' = cal_x1(left,right') = cal_x2(left,x1)

Разве не в этом прелесть симметрии в математике? Точно так же мы могли бы показать это x2' = cal_x2(left',right) = cal_x1(x1',right). Таким образом, он дает нам код ниже.

Я считаю, что эта картина лучше всего резюмирует мои предыдущие выводы. Помните, что проблема, которую мы решили, является частным случаем, когда и ввод, и вывод являются дискретными целыми значениями. Сам алгоритм также может применяться для поиска min / max для непрерывных унимодальных функций. Если обратить внимание на уменьшение пространства поиска после каждой итерации: скорость сходимости постоянна 1 / ϕ = 0,61803 (пространство поиска уменьшается на 38,196% на каждой итерации). В то время как бинарный поиск (поиск пополам) сходится линейно со скоростью 1/2.

Поиск по золотому сечению и бинарный поиск обычно имеют разные варианты использования:
1) бинарный поиск отсортированного массива; 2) поиск по золотому сечению унимодальной функции в заданном диапазоне. Замечательно работать над примером, в котором можно применить два алгоритма поиска.

В заключение я поделюсь менее актуальным, но очень кратким решением, чтобы показать красоту Python как языка программирования:

Ссылка