Почему это работает
- Если разрезать повёрнутый массив на mid, хотя бы одна сторона растёт без спуска. nums[lo] <= nums[mid] значит, что левая, иначе — правая.
- В растущем куске лежат ровно значения между его краями, поэтому одна проверка показывает, может ли там быть искомое. Если да, оставляем эту половину, если нет — оно может быть только в другой.
- В любом случае половина диапазона уходит, как в обычном бинарном поиске. Здесь первый шаг отбрасывает левую половину 12..31, а второй находит 5 между 2 и 9.
Сложность
Время O(log n): каждый шаг делит диапазон пополам. Память O(1): три индекса.
дальшеТеперь реши её сам, без подсказок.
Решить на LeetCode ↗