visual walkthrough
Find Minimum in Rotated Sorted Array
Compare with the right end to find the pivot.
The idea
A turned sorted array is two sorted runs. Everything in the first run is bigger than everything in the second, and the minimum starts the second run.
Comparing arr[mid] with arr[hi] tells you which run mid is in, so you can drop half.
Complexity
| approach | time | space |
|---|---|---|
| Scan for the smallest | O(n) | O(1) |
| Binary search for the drop | O(log n) | O(1) |