Почему это работает
- Повёрнутый отсортированный массив растёт, один раз падает и снова растёт. Минимум стоит сразу после спуска или на индексе 0, если спуска нет.
- Сравниваем середину с правым краем. Если nums[mid] > nums[hi], спуск между ними, и минимум правее mid. Если нет, mid..hi растёт без спуска, и минимум — mid или левее.
- Во втором случае hi = mid, а не mid − 1: mid сам может быть минимумом. Здесь уже первый mid попадает на 3, и диапазон потом сходится к нему.
Сложность
Время O(log n): каждый шаг делит диапазон пополам. Память O(1): три индекса.
дальшеТеперь реши её сам, без подсказок.
Решить на LeetCode ↗