Why it works
- A rotated sorted array rises, drops once and rises again. The minimum is right after the drop, or at index 0 if there is no drop.
- Compare the middle with the right end. If nums[mid] > nums[hi], the drop is between them, so the minimum is after mid. If not, mid..hi rises with no drop, so the minimum is mid or before it.
- In the second case hi = mid, not mid − 1: mid may be the minimum itself. Here the very first mid lands on 3, and the range then closes on it.
Complexity
Time O(log n): every step halves the range. Memory O(1): three indices.
nextNow solve it yourself, no hints.
Solve on LeetCode ↗