Поиск в отсортированном массиве целых, который переворачивается

Question

Есть ли простой способ поиска в массиве, подобном этому?Некоторые примеры ниже:

5 6 7 8 19 45 21 32 40  // Rolled over at 7 th element
15 22 32 45 121 341 40  // Rolled over at 7 th element
1 22 32 45 121 341 400  // Rolled over at 0 th element

Answer 1

Любой алгоритм для нахождения точки "опрокидывания" в худшем случае будет иметь как минимум сложность O (n).

Представьте, вы отсортировали массив и проверили менее n его элементов. Например, если в массиве 1 2 3 4 5 6 7 8 9 10 вы не проверяли элемент 4, я могу заменить его на 100 и создать «ролловер» (1 2 3 100 5 6 7 8 9 10). Ваш алгоритм не будет знать, так как он никогда не читает этот элемент.

Таким образом, ваш единственный вариант - пройти через все элементы, пока вы не найдете опрокидывание.

Спасибо Эялю Шнайдеру за полезный комментарий.

Кстати, я здесь единственный, кто не понимает этимологию слова «опрокидывание»?

Answer 2

Если вы собираетесь выполнять много поисков, вы можете сделать один проход предварительной обработки, используя линейный поиск, чтобы получить индексы всех мест прокрутки, а затем выполнить двоичный поиск в каждом разделе.

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

Если вы используете метод «сначала найти ролловер» и знаете, что есть только одна точка ролловера, вы можете по крайней мере выйти из этого линейного поиска, как только найдете точку.

Answer 3

это должно помочь http://geeksforgeeks.org/?p=1068

Answer 4

Думайте о вашем массиве как о математической функции, то, что вы хотите, это локальные максимумы вашей функции. Хотя у меня недостаточно знаний, чтобы объяснить, вы можете провести исследование о Hill Climbing . Используя некоторую эвристику, вы сможете найти свои локальные максимумы более эффективно.