Search in Rotated Sorted Array
Search for a target in a rotated sorted array.
Search a target in a rotated sorted array in O(log n). The key is recognizing that at least one half remains sorted after every split.
Pattern fit
At every step one half is still sorted, so binary search becomes a matter of detecting which half is ordered and whether the target belongs there.
Key observation
You are not comparing target with random values; you are using sorted-half structure to eliminate half the array safely.
Target complexity
O(log n) / O(1)
How to break down the solution cleanly
Binary search as usual, but first determine which half is sorted.
If the left half is sorted, check whether target lies inside that ordered interval.
Otherwise the right half must be sorted, so test target against that interval instead.
Discard the half that cannot possibly contain target and continue.
Walk through one example
Example: nums = [4,5,6,7,0,1,2], target = 0.
mid points to 7, and the left half [4,5,6,7] is sorted.
Target 0 is not inside that half, so move to the right half.
Repeat once more and you land on index 4.
Reference implementation
Pythondef search(nums: list[int], target: int) -> int:
left, right = 0, len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] == target:
return mid
if nums[left] <= nums[mid]:
if nums[left] <= target < nums[mid]:
right = mid - 1
else:
left = mid + 1
else:
if nums[mid] < target <= nums[right]:
left = mid + 1
else:
right = mid - 1
return -1
Common pitfalls
Failing to distinguish which half is sorted before moving pointers.
Using standard binary-search branches without respecting rotation structure.
Common follow-ups
How does the duplicate-value version change?
What invariant stays true after each branch?
Continue with related problems
Build repeatable depth inside the Binary Search cluster before moving on.