Why it works
- Cut a rotated array at mid, and at least one side rises with no drop. nums[lo] <= nums[mid] means the left side does; otherwise the right side does.
- A rising piece holds exactly the values between its ends, so one check tells whether the target can be in it. If yes, keep that half; if not, the target can only be in the other one.
- Either way half the range goes, as in plain binary search. Here the first step drops the left half 12..31, and the second finds 5 between 2 and 9.
Complexity
Time O(log n): every step halves the range. Memory O(1): three indices.
nextNow solve it yourself, no hints.
Solve on LeetCode ↗