Почему это работает
- За краями −∞, поэтому, идя в гору, всегда упрёшься в пик: склон не может расти бесконечно и обязан повернуть вниз, самое позднее за концом.
- Если nums[mid] < nums[mid + 1], справа подъём, и пик правее mid. Если нет, справа спуск: либо mid — пик, либо влево от него подъём, так что пик на mid или левее.
- Годится любой пик, поэтому можно отбросить половину, где тоже есть пик. Здесь первый шаг отбрасывает половину с 8 и поднимается к 9.
Сложность
Время O(log n): каждый шаг делит диапазон пополам. Память O(1): три индекса.
дальшеТеперь реши её сам, без подсказок.
Решить на LeetCode ↗