Поиск указанного элемента в упорядоченном массиве со сдвигом

Имеется отсортированный по возрастанию массив из n целых чисел, который был циклически сдвинут неизвестное число раз. Требует найти индекс определенного элемента в массиве.

https://en.wikipedia.org/wiki/Binary_search_algorithm

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

Массив отсортирован, первая мысль — бинарный поиск,O(log n) . Однако, массив был циклически сдвинут неизвестное число раз, поэтому нельзя искать относительно текущего центра.

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

Эта особенность позволяет выбрать половину для поиска.

Пример:

[10, 15, 20, 0, 5]
[50, 5, 20, 30, 40]

Если мы ищем 5 в первом массиве, то посмотрим на крайний левый и центральный элементы: 20 > 10 , становится понятно, что левая половина отсортирована. 5 не попадает в этот диапазон, поэтому искать нужно справа.

Во втором примере 50 > 20 , а значит отсортирована другая, правая половина. Проверим центральный и крайний правый элемент: становится ясно, что 5 не попадает в этот диапазон, поэтому искать нужно слева.

Есть краевой случай: когда левая половина состоит из повторов.

[2, 2, 2, 3, 4, 2]

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

Заметим, что случая когда правая половина состоит из повторов не может быть, иначе бы нарушилось условие задачи — массив изначально отсортирован по возрастанию.

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

Особое внимание стоит уделить выбору границ при повторном поиске: сmid +/- 1 легко запутаться.


Это решения задач из книги Cracking the Coding Interview. Все опубликованные мною решения можно найти по фильтру.