Search in Rotated Sorted Array
Learn how to binary search an array that has been rotated at an unknown pivot point.
Search in Rotated Sorted Array
A rotated sorted array is a sorted array that has been split at some pivot point and the two halves have been swapped. For example [1,3,5,7,9,11,13] rotated at index 4 becomes [9,11,13,1,3,5,7]. The array is no longer globally sorted, but each half is still locally sorted.
Original sorted: [1, 3, 5, 7, 9, 11, 13]
Rotated at 4: [9, 11, 13, 1, 3, 5, 7]
↑ left half ↑ ↑ right half ↑The challenge — find a target value in O(log n) time, without knowing where the rotation point is.
The key insight
At every step of binary search, at least one half of the current window is always sorted. Check which half is sorted by comparing arr[left] and arr[mid]. Then decide whether the target falls within the sorted half — if yes, search there. If no, search the other half.
def search_rotated(arr, target):
left, right = 0, len(arr) - 1
while left <= right:
mid = left + (right - left) // 2
if arr[mid] == target:
return mid
# left half is sorted
if arr[left] <= arr[mid]:
if arr[left] <= target < arr[mid]:
right = mid - 1 # target is in the sorted left half
else:
left = mid + 1 # target is in the right half
# right half is sorted
else:
if arr[mid] < target <= arr[right]:
left = mid + 1 # target is in the sorted right half
else:
right = mid - 1 # target is in the left half
return -1
arr = [9, 11, 13, 1, 3, 5, 7]
print(search_rotated(arr, 3)) # 4
print(search_rotated(arr, 11)) # 1
print(search_rotated(arr, 6)) # -1Tracing through an example
arr = [9, 11, 13, 1, 3, 5, 7], target = 3
Step 1: left=0, right=6, mid=3
arr[3]=1 ≠ 3
arr[left]=9 > arr[mid]=1 → right half [1..6] is sorted
target=3 in range (arr[3]=1, arr[6]=7]? Yes
→ search right: left = 4
Step 2: left=4, right=6, mid=5
arr[5]=5 ≠ 3
arr[left]=3 < arr[mid]=5 → left half [4..5] is sorted
target=3 in range [arr[4]=3, arr[5]=5)? Yes (3 == 3)
→ search left: right = 4
Step 3: left=4, right=4, mid=4
arr[4]=3 == 3 → return 4 ✓Finding the rotation point
Sometimes you need to find the pivot — the index of the smallest element (where the rotation happened):
def find_rotation_pivot(arr):
"""Find the index of the minimum element."""
left, right = 0, len(arr) - 1
if arr[left] <= arr[right]:
return 0 # array is not rotated
while left < right:
mid = left + (right - left) // 2
if arr[mid] > arr[right]:
left = mid + 1 # pivot is in the right half
else:
right = mid # pivot is at mid or left of mid
return left # index of minimum element
arr = [9, 11, 13, 1, 3, 5, 7]
print(find_rotation_pivot(arr)) # 3 — arr[3]=1 is minimumOnce you know the pivot, you can binary search each half independently.
With duplicates
If the array contains duplicates, the approach needs a small tweak — when arr[left] == arr[mid], you cannot determine which half is sorted, so you must fall back to linear elimination:
def search_rotated_with_duplicates(arr, target):
left, right = 0, len(arr) - 1
while left <= right:
mid = left + (right - left) // 2
if arr[mid] == target:
return True
# cannot determine sorted half — shrink window by one
if arr[left] == arr[mid] == arr[right]:
left += 1
right -= 1
elif arr[left] <= arr[mid]:
if arr[left] <= target < arr[mid]:
right = mid - 1
else:
left = mid + 1
else:
if arr[mid] < target <= arr[right]:
left = mid + 1
else:
right = mid - 1
return FalseWith duplicates, worst-case performance degrades to O(n) because the arr[left] == arr[mid] condition can trigger n/2 times. This is a known limitation — without duplicates, the algorithm maintains O(log n).
Why this problem matters
Rotated array search appears frequently in technical interviews. It tests whether you can adapt binary search beyond the simple "sorted array" case — the key skill is recognizing that at every step, at least one half is always sorted, and using that property to decide where to search.
Complexity
| Case | Time | Space |
|---|---|---|
| No duplicates | O(log n) | O(1) |
| With duplicates (worst case) | O(n) | O(1) |