Practice › Binary Search
Search in Rotated Sorted Array
Medium · Binary Search · Asked at Amazon, Microsoft, Google, Adobe, Paytm
A sorted array of distinct values was rotated at some unknown pivot (e.g. [0,1,2,4,5,6,7] → [4,5,6,7,0,1,2]). Print the index of x, or -1.
Input
First line: n. Second line: n distinct integers. Third line: x.
Output
The index of x, or -1.
Constraints
- 1 ≤ n ≤ 10^5
In every step one half is sorted — check whether x lies in that half. O(log n).
Example 1
Input
7 4 5 6 7 0 1 2 0
Output
4
Example 2
Input
7 4 5 6 7 0 1 2 3
Output
-1
Hints
- Cut a rotated sorted array anywhere and at least one half is still sorted.
- Compare a[lo] with a[mid] to see which half is sorted, then check whether x lies inside that half's range.
Approach
Normal binary search plus one decision. If a[lo] <= a[mid], the left half [lo, mid] is sorted: if a[lo] <= x < a[mid] search left, otherwise search right. If not, the right half [mid, hi] is sorted: if a[mid] < x <= a[hi] search right, otherwise left. The values are distinct, so the sorted half can always be identified.
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 &v : a) cin >> v;
long long x;
cin >> x;
int lo = 0, hi = n - 1, ans = -1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (a[mid] == x) { ans = mid; break; }
if (a[lo] <= a[mid]) {
if (a[lo] <= x && x < a[mid]) hi = mid - 1;
else lo = mid + 1;
} else {
if (a[mid] < x && x <= a[hi]) lo = mid + 1;
else hi = mid - 1;
}
}
cout << ans << "\n";
return 0;
}Python solution
import sys
data = list(map(int, sys.stdin.read().split()))
n = data[0]
a, x = data[1 : n + 1], data[n + 1]
lo, hi, ans = 0, n - 1, -1
while lo <= hi:
mid = (lo + hi) // 2
if a[mid] == x:
ans = mid
break
if a[lo] <= a[mid]:
if a[lo] <= x < a[mid]:
hi = mid - 1
else:
lo = mid + 1
else:
if a[mid] < x <= a[hi]:
lo = mid + 1
else:
hi = mid - 1
print(ans)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();
long x = sc.nextLong();
int lo = 0, hi = n - 1, ans = -1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (a[mid] == x) { ans = mid; break; }
if (a[lo] <= a[mid]) {
if (a[lo] <= x && x < a[mid]) hi = mid - 1;
else lo = mid + 1;
} else {
if (a[mid] < x && x <= a[hi]) lo = mid + 1;
else hi = mid - 1;
}
}
System.out.println(ans);
}
}Solve Search in Rotated Sorted Array online · All practice problems