Search in Rotated Sorted Array

Проверяйте каждый индекс по порядку и возвращайте первый, значение которого равно target. Если цикл заканчивается без совпадения, верните -1. Значения различны, поэтому первое совпадение — единственное, и такой просмотр корректен для любого списка, повёрнутого или нет.

Этот подход игнорирует всё, что сообщает вам условие задачи. Список состоит из двух отсортированных последовательностей, но при просмотре приходится считывать до всех 5000 элементов, тогда как для бинарного поиска нужно около 13 сравнений. С ростом входных данных разрыв увеличивается: для миллиона элементов требуется миллион сравнений, а бинарному поиску — около 20. В задаче требуется O(log n), поэтому этот подход — исходный вариант, который нужно улучшить, а не ответ.

Повернутый список состоит из двух отсортированных участков, и второй начинается с наименьшего значения. Обозначим его индекс через k. Зная k, мы сводим задачу к обычному бинарному поиску: nums[k..n-1] отсортирован и содержит значения от nums[k] до nums[n-1], а nums[0..k-1] отсортирован и содержит все значения больше. Одно сравнение target с nums[k] и nums[n-1] позволяет выбрать участок для поиска.

Чтобы найти k, выполним бинарный поиск места разрыва. Сравним среднее значение с последним значением диапазона — nums[hi]. Если nums[mid] > nums[hi], где-то после mid значения убывают, значит, наименьшее значение находится справа: зададим lo = mid + 1. В противном случае nums[mid..hi] возрастает без разрыва, поэтому наименьшее значение находится на позиции mid или левее: зададим hi = mid, оставив mid в диапазоне. Когда lo сравняется с hi, этот индекс и будет k.

Проследим за первым примером: [15, 19, 23, 2, 5, 8, 11] с target = 5. Среднее значение 2 не больше 11, поэтому hi становится равным 3; затем 19 больше 2, поэтому lo становится равным 2; затем 23 больше 2, поэтому lo становится равным 3, и k = 3. Поскольку 5 находится между nums[3] = 2 и nums[6] = 11, ищем в индексах от 3 до 6, где бинарный поиск находит 5 по индексу 4. Два бинарных поиска требуют примерно 2 log2 n шагов.

Не нужно знать, где находится точка поворота. Сохраняется обычное обещание бинарного поиска: если target есть в списке, его индекс находится между lo и hi. Посмотри на средний индекс mid. Значения уменьшаются только один раз во всём списке, поэтому это уменьшение встречается не более чем в одной из двух половин относительно mid, а другая половина отсортирована.

Найди отсортированную половину с помощью одного сравнения. Если nums[lo] ≤ nums[mid], левая половина nums[lo..mid] не содержит уменьшения и отсортирована. Поскольку ты уже знаешь, что nums[mid] не равно target, target может находиться в этой половине, только если nums[lo] ≤ target < nums[mid]. Если это так, установи hi = mid - 1; если нет, target может находиться только в другой половине, поэтому установи lo = mid + 1. Когда nums[lo] > nums[mid], уменьшение находится слева, правая половина nums[mid..hi] отсортирована, и решение определяет зеркальная проверка nums[mid] < target ≤ nums[hi]. Ты никогда не рассуждаешь напрямую о неотсортированной половине: target попадает в неё ровно тогда, когда не может находиться в отсортированной половине.

Проследи за первым примером: [15, 19, 23, 2, 5, 8, 11] с target = 5. Диапазон от 0 до 6 имеет середину 3 со значением 2. Поскольку 15 больше 2, правая половина [2, 5, 8, 11] отсортирована, и в ней есть 5, поэтому lo становится равным 4. У диапазона от 4 до 6 середина 5 со значением 8. Теперь nums[4] = 5 ≤ 8, левая половина [5, 8] отсортирована и содержит 5, поэтому hi становится равным 4. По индексу 4 находится 5: верни 4.

На каждом шаге диапазон сокращается вдвое, как при обычном бинарном поиске, поэтому цикл выполняется не более примерно log2(n) + 1 раз: 13 шагов для 5000 элементов, с использованием дополнительной памяти для двух индексов.