IntermediateBinary Search
Searching a rotated sorted array
After rotation, one half around mid is always sorted. Check whether the target lies in that half; if not, it's in the other.
The idea
A rotated sorted array like [4,5,6,7,0,1,2] isn't fully sorted, but if you cut it at any mid, at least one side is. You can tell which by comparing the ends: if nums[lo] ≤ nums[mid], the left side is sorted.
In the sorted side you can check in O(1) whether the target fits between its ends. That tells you which half to keep, so it's still O(log n).
Worked example
Find 0 in [4, 5, 6, 7, 0, 1, 2]
- lo=0 (4), mid=3 (7): left 4…7 is sorted, 0 isn't in it → go right, lo = 4
- lo=4 (0), hi=6 (2), mid=5 (1): left 0…1 sorted, 0 is in it → hi = 4
- mid=4 → 0 found
In code (Python)
def search(nums, target):
lo, hi = 0, len(nums) - 1
while lo <= hi:
mid = (lo + hi) // 2
if nums[mid] == target:
return mid
if nums[lo] <= nums[mid]: # left half sorted
if nums[lo] <= target < nums[mid]:
hi = mid - 1
else:
lo = mid + 1
else: # right half sorted
if nums[mid] < target <= nums[hi]:
lo = mid + 1
else:
hi = mid - 1
return -1O(log n) time, O(1) space.
How to spot it
- “rotated sorted array”, or sorted data that wraps around.
Common mistakes
- Using < instead of <= in nums[lo] <= nums[mid] (breaks when lo == mid).
- Mixing up which bound is inclusive in the range checks.
Practise it
Go further
Up next for you · Beginner
“Have I seen this?” is a set →