Бинарный поиск в повёрнутом отсортированном массиве

В двух прошлых уроках список был отсортирован целиком, от меньшего к большему. Бинарный поиск работал, потому что по средней ячейке всегда было видно, в какой половине искомое значение (target). Теперь список тоже отсортирован, но его повернули: разрезали в одном месте и поменяли два куска местами.

Возьми [4, 5, 6, 7, 0, 1, 2]. Числа растут 4, 5, 6, 7, потом падают до 0, потом снова растут 1, 2. Это список [0, 1, 2, 4, 5, 6, 7], повёрнутый так, что первым стоит 4. Все числа по-прежнему разные, и внутри каждого куска они идут по возрастанию. Где именно падение, ты не знаешь.

Нужно найти индекс значения за O(log n), так же быстро, как обычным бинарным поиском. Проход по всем ячейкам занял бы O(n) и никак не использовал бы порядок, который в списке остался.

Ищем 0 в [4, 5, 6, 7, 0, 1, 2]. Посередине стоит 7. Слева от неё 4, 5, 6, 7: числа растут без падения. Значит, левая половина отсортирована, и в ней лежат только числа от 4 до 7. Ноля среди них быть не может. Значит, он справа: [0, 1, 2].

Так работает каждый шаг. Ты делишь список пополам. Одна из половин всегда идёт ровно по порядку, без падения внутри. По её первому и последнему числу видно, какие числа в ней есть. Если искомое число попадает в этот промежуток, ищи в этой половине. Если нет, ищи в другой. В обоих случаях половина чисел отбрасывается.

Держи две границы, lo и hi, и бери середину mid. Если nums[mid] равно target, поиск закончен. Если нет, надо выбрать сторону. Массив не отсортирован целиком, поэтому одного сравнения target с серединой не хватает.

Опорный факт: при любом mid хотя бы одна из двух половин отсортирована целиком, без падения внутри. Чтобы узнать какая, сравни nums[lo] с nums[mid]. Если nums[lo] <= nums[mid], отсортирована левая половина. Иначе падение лежит слева, и отсортирована правая. Теперь у тебя есть половина, для которой ты точно знаешь промежуток значений. Если target в него попадает, переходи в эту половину. Если нет, переходи в другую.

Проследим на [4, 5, 6, 7, 0, 1, 2], ищем 0:

• Начало: lo = 0, hi = 6, mid = 3, nums[mid] = 7. Это не 0. nums[lo] = 4 <= 7, значит, левая половина 4..7 отсортирована. 0 не лежит в 4..7, поэтому идём вправо: lo = 4.
• Теперь lo = 4, hi = 6, mid = 5, nums[mid] = 1. Это не 0. nums[lo] = 0 <= 1, значит, левая половина 0..1 отсортирована. 0 лежит в ней, поэтому идём влево: hi = 4.
• Теперь lo = 4, hi = 4, mid = 4, nums[4] = 0. Совпало, возвращаем 4.

Время: O(log n). Каждый шаг, как в обычном бинарном поиске, отбрасывает половину оставшегося. На шаг добавляется пара сравнений, чтобы выбрать отсортированную половину. Это O(1), и число шагов от них не меняется.

Память: O(1). Ты хранишь lo, hi и mid, и ничего из этого не растёт с размером входа.

Кольцевой буфер (массив постоянного размера, который заполняется по кругу) записывает данные по порядку. Дойдя до конца, он продолжает с начала, и место перехода заранее неизвестно. Поэтому сохранённый массив оказывается повёрнутым отсортированным массивом, и поиск значения в нём работает так же. Ещё пример: чтение кольцевого лога по метке времени или номеру записи без прохода по всему логу. В целом этот поиск подходит любой структуре, которая хранит данные по порядку, но начинается с меняющегося места, когда поиск всё равно должен идти за O(log n).