Search in Rotated Array
Medium · rating 1550 · Binary Search, Arrays
The first line has n. The second line has n distinct integers: a sorted array that has been rotated at some pivot. The third line has a target. Print its 0-based index, or -1 if absent.
Constraints: 1 ≤ n ≤ 105
Editorial
Approach
Binary search still works on a rotated sorted array: at each midpoint, one of the two halves is guaranteed to be in normal sorted order. Check whether the target lies within that sorted half — if so, search it; otherwise search the other half.
Spotting the sorted half
If a[lo] ≤ a[mid] the left half is sorted; use its bounds to decide. Otherwise the right half is sorted. Either way half the array is discarded each step.
if a[lo] <= a[mid]:
if a[lo] <= t < a[mid]: hi = mid-1
else: lo = mid+1
else:
if a[mid] < t <= a[hi]: lo = mid+1
else: hi = mid-1Complexity
Time: O(log n). Space: O(1).
Related problems
- Minimum in Rotated Array — Medium
- Search Insert Position — Medium
- Longest Increasing Subsequence — Hard
- Maximum Product Subarray — Hard
- Next Permutation — Medium
- Subarrays Summing to K — Hard