Search in Rotated Sorted Array
Picture
[4,5,6,7,0,1,2] has one break. We seek 0 without scanning every value.
Predict
Can duplicate values hide which half is sorted?
Walk through the small example
Yes. At least one half remains normally sorted; its bounds reveal whether it can contain the target.
Mental model and complete Python solution
Rotation breaks global order once, but any middle point leaves at least one ordinary sorted half. Use that half as evidence, not the visual position of the target.
What the function promises: Return the target index or -1. Values are distinct and were produced by rotating a strictly increasing list.
def rotated_index(values, target):
left, right = 0, len(values) - 1
while left <= right:
middle = (left + right) // 2
if values[middle] == target:
return middle
if values[left] <= values[middle]:
if values[left] <= target < values[middle]:
right = middle - 1
else:
left = middle + 1
elif values[middle] < target <= values[right]:
left = middle + 1
else:
right = middle - 1
return -1
assert rotated_index([4,5,6,7,0,1,2], 0) == 4
assert rotated_index([4,5,6,7,0,1,2], 3) == -1
Work and storage: O(log n) time and O(1) space under the distinct-value contract.
When to recognize it: At least one half remains normally sorted; its bounds reveal whether it can contain the target.
Check before applying it: With duplicates, equal endpoints can make the useful half ambiguous and force linear shrinking.
Change one rule
Duplicates are allowed.
See what changes
When left, middle, and right are equal, shrink an endpoint; worst-case time becomes O(n).
Connect
Binary search: find a boundary: Keep a search interval and justify every discarded half.
invariants: The target, if present, remains inside the interval.