Minimum in Rotated Array
Medium · rating 1450 · Binary Search, Arrays
The first line has n. The second line has n distinct integers: a sorted array rotated at some pivot. Print the minimum value.
Constraints: 1 ≤ n ≤ 105
Editorial
Approach
Binary search on the rotation. Compare the midpoint to the right end: if a[mid] > a[hi] the minimum must be to the right of mid; otherwise it's at mid or to its left. The window shrinks to the single smallest element.
lo, hi = 0, n-1
while lo < hi:
m = (lo + hi) // 2
if a[m] > a[hi]: lo = m + 1
else: hi = m
return a[lo]Complexity
Time: O(log n). Space: O(1).
Related problems
- Search in Rotated Array — Medium
- Search Insert Position — Medium
- Next Greater Element — Medium
- Product of Array Except Self — Hard
- Count Pairs With Difference — Medium
- Count Pairs with Sum — Medium