Practice › Binary Search
Minimum in Rotated Sorted Array
Medium · Binary Search · Asked at Amazon, Microsoft, Google, Meta
A sorted array of distinct values was rotated at an unknown point (e.g. [3,4,5,1,2]). Print its minimum element in O(log n).
Input
First line: n. Second line: n space-separated integers.
Output
The minimum value.
Constraints
- 1 ≤ n ≤ 10^5
- -10^9 ≤ a[i] ≤ 10^9
Compare a[mid] with a[high]: if a[mid] > a[high], the minimum is to the right of mid; otherwise it is at mid or to its left.
Example 1
Input
5 3 4 5 1 2
Output
1
Example 2
Input
4 11 13 15 17
Output
11
Hints
- Compare the middle element with the last element of the current range.
- If a[mid] > a[hi], the drop (and the minimum) is to the right of mid; otherwise the minimum is at mid or to its left.
Approach
Binary search with lo = 0, hi = n − 1. While lo < hi: if a[mid] > a[hi], the rotation point is after mid, so lo = mid + 1; otherwise [mid, hi] is sorted and the minimum is at mid or before, so hi = mid. When they meet, a[lo] is the minimum. Comparing with a[hi] (not a[lo]) also handles arrays that are not rotated at all.
Complexity: O(log n) time · O(1) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
vector<long long> a(n);
for (auto &x : a) cin >> x;
int lo = 0, hi = n - 1;
while (lo < hi) {
int mid = (lo + hi) / 2;
if (a[mid] > a[hi]) lo = mid + 1;
else hi = mid;
}
cout << a[lo] << "\n";
return 0;
}Python solution
import sys
data = list(map(int, sys.stdin.read().split()))
a = data[1:]
lo, hi = 0, len(a) - 1
while lo < hi:
mid = (lo + hi) // 2
if a[mid] > a[hi]:
lo = mid + 1
else:
hi = mid
print(a[lo])Java solution
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
long[] a = new long[n];
for (int i = 0; i < n; i++) a[i] = sc.nextLong();
int lo = 0, hi = n - 1;
while (lo < hi) {
int mid = (lo + hi) / 2;
if (a[mid] > a[hi]) lo = mid + 1;
else hi = mid;
}
System.out.println(a[lo]);
}
}Solve Minimum in Rotated Sorted Array online · All practice problems