Код Senior Бинарный поиск обновлено
Поиск в повёрнутом массиве
Условие
Отсортированный массив повернули вокруг неизвестной точки. Найди индекс target, иначе -1.
Примеры
search([4, 5, 6, 7, 0, 1, 2], 0) // 4
search([4, 5, 6, 7, 0, 1, 2], 3) // -1
search([1], 1) // 0
Как подойти
Ключевое наблюдение: при любом разрезе хотя бы одна половина отсортирована. Определяем её сравнением nums[lo] <= nums[mid], затем решаем, в какой половине искать. Нестрогое сравнение важно для массива из двух элементов.
Подсказки: 2
- Одна из половин всегда отсортирована.
- Определи, какая, и проверь, попадает ли target в её диапазон.
Решите в тренажёре
Редактор с автотестами прямо в браузере. Можно решить спокойно, вслух или под таймером, как на собесе.