Rotated sorted arrays
In one line
A rotated sorted array is two sorted runs glued together; at every mid point at least one half is still sorted, so you can check that half and keep binary searching in O(log n).
What it is
A rotated sorted array is a sorted array that has been cut at some point and the two pieces swapped. [0, 1, 2, 4, 5, 6, 7] rotated at index 4 becomes [4, 5, 6, 7, 0, 1, 2]. It is no longer fully sorted, so classic binary search can go the wrong way.
The key fact is that when you split it at any mid, at least one side, [lo..mid] or [mid..hi], is a normal sorted run. You can tell which by comparing the end values, check whether the target lies inside that sorted run, and discard the other side. The rotation point itself (the minimum) can also be found by binary search.
Why interviewers ask
This is a standard test of whether you understand why binary search works rather than memorising a template. You must reason about which half is sorted, write correct inclusive and exclusive comparisons, and handle edge cases such as no rotation, two elements and duplicates. Interviewers often follow up with 'what if there are duplicates?', which changes the worst case to O(n).
How it works
- 1Set lo = 0 and hi = n - 1 and loop while lo <= hi. Compute mid; if nums[mid] is the target, return mid.
- 2If nums[lo] <= nums[mid], the left half [lo..mid] is sorted (no rotation point inside it).
- 3In that case, if nums[lo] <= target < nums[mid], the target can only be in the left half: hi = mid - 1. Otherwise it is in the right half: lo = mid + 1.
- 4Otherwise the right half [mid..hi] is sorted. If nums[mid] < target <= nums[hi], go right: lo = mid + 1. Otherwise go left: hi = mid - 1.
- 5To find the minimum (the rotation point), compare nums[mid] with nums[hi]: if nums[mid] > nums[hi], the drop is to the right, so lo = mid + 1; otherwise the minimum is at mid or to its left, so hi = mid. Stop when lo == hi.
- 6With duplicates, nums[lo] == nums[mid] == nums[hi] gives no information about which side is sorted; shrink by one (lo += 1, hi -= 1), which makes the worst case O(n).
Worked example · Find 0 in [4, 5, 6, 7, 0, 1, 2]
- lo = 0, hi = 6, mid = 3, nums[3] = 7. Not the target. nums[0] = 4 <= 7, so the left half [4, 5, 6, 7] is sorted.
- Is 4 <= 0 < 7? No, so 0 is not in the sorted left half: lo = 4.
- lo = 4, hi = 6, mid = 5, nums[5] = 1. nums[4] = 0 <= 1, so the left half [0, 1] is sorted. Is 0 <= 0 < 1? Yes: hi = 4.
- lo = 4, hi = 4, mid = 4, nums[4] = 0. Found at index 4 after 3 comparisons.
- Finding the minimum of the same array: lo = 0, hi = 6, mid = 3, 7 > 2 so lo = 4; mid = 5, 1 <= 2 so hi = 5; mid = 4, 0 <= 1 so hi = 4. lo == hi == 4: minimum 0 at index 4, which is also the rotation amount.
Picture it
A clock face: the numbers go up all the way around and then wrap from 12 back to 1. If you look at any arc that does not cross the 12-to-1 jump, it is perfectly ordered, and it is easy to tell whether your number lies on that arc.
Reference code
def search_rotated(nums, target):
"""Search a rotated sorted array of distinct values. Return index or -1."""
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 [lo..mid] is sorted
if nums[lo] <= target < nums[mid]:
hi = mid - 1
else:
lo = mid + 1
else: # right half [mid..hi] is sorted
if nums[mid] < target <= nums[hi]:
lo = mid + 1
else:
hi = mid - 1
return -1
def find_min_rotated(nums):
"""Smallest value (the rotation point) of a rotated sorted array, distinct values."""
lo, hi = 0, len(nums) - 1
while lo < hi:
mid = (lo + hi) // 2
if nums[mid] > nums[hi]:
lo = mid + 1 # minimum is right of mid
else:
hi = mid # mid may be the minimum
return nums[lo]
search_rotated keeps the closed-range template and only changes how it picks a side: it first identifies the sorted half, then checks whether the target fits inside that half. find_min_rotated compares with nums[hi] because the right end tells you whether the drop is to the right of mid. Both are O(log n) time and O(1) space for distinct values.
Key patterns
Search target in rotated array
When: Distinct values, find the index of a target
How: Decide which half is sorted with nums[lo] <= nums[mid], check if the target is inside it, discard the other half.
Find minimum / rotation count
When: Find the smallest element or how many times the array was rotated
How: Compare nums[mid] with nums[hi]; lo = mid + 1 if greater, else hi = mid. The index of the minimum equals the rotation count.
Find pivot then classic search
When: You prefer two simple searches over one tricky one
How: Find the minimum index k, then run classic binary search on [0, k - 1] or [k, n - 1] depending on the target.
Duplicates allowed
When: Values can repeat, such as [2, 2, 2, 0, 2]
How: When nums[lo], nums[mid] and nums[hi] are equal, shrink the ends by one. Correct, but the worst case becomes O(n).
Real-world use
Consistent hashing rings
Systems like Apache Cassandra and Amazon Dynamo-style stores place nodes on a hash ring kept as a sorted list of tokens. A key goes to the first token >= its hash, wrapping to the start of the list when it passes the end: binary search on a circular sorted order.
Circular logs on flash storage
Embedded devices often write records with increasing sequence numbers into a fixed circular region of flash. After a reboot the firmware binary searches the region for the wrap point (the oldest or newest record) instead of reading every block.
Ring buffers of time-stamped data
Metrics agents and in-memory trace buffers overwrite the oldest entry when full, so the stored timestamps form a rotated sorted array; finding the start, or the first sample after a time, is a rotated binary search.
In a project
An IoT sensor keeps the last 65,536 readings in a circular buffer in flash, each with an increasing sequence number. After a power cut, the device must find the newest reading to resume writing, and a full scan takes too long on the slow flash.
- Treat the sequence numbers in slot order as a rotated sorted array: they increase and then drop once at the wrap point.
- Binary search for the minimum with the nums[mid] > nums[hi] rule; the slot before it holds the newest reading.
- Handle the never-wrapped case (array already sorted) and empty or erased slots explicitly, for example by treating erased slots as invalid and checking the first slot.
- Test with the wrap point at 0, in the middle and at the last slot, and with a buffer that is only partly filled.
Impact: Recovery reads about 16 slots instead of 65,536, so boot time after a power cut drops from seconds to milliseconds and flash wear from reads is negligible.
Trade-offs
Use it when
- A sorted array has been rotated, or data is stored in a circular buffer in order
- Values are distinct, so the O(log n) guarantee holds
- You need the rotation point (oldest entry, wrap position)
Avoid it when
- There are many duplicates: worst case is O(n), so a linear scan may be just as good and simpler
- You control the storage: keep a separate head index for the ring buffer and avoid searching at all
- The array is not rotated sorted at all (more than one drop)
Cost: O(log n) time, O(1) space with distinct values; O(n) worst case with duplicates.
Common mistakes
- Using nums[lo] < nums[mid] instead of <=, which picks the wrong half when lo == mid (two elements left).
- Getting the range checks wrong: the sorted-half test must include the end that is known (nums[lo] <= target) and exclude mid, which was already checked.
- Finding the minimum by comparing nums[mid] with nums[lo]: it fails on an unrotated array; compare with nums[hi] instead.
- Claiming O(log n) with duplicates: [1, 1, 1, 1, 0, 1, 1] cannot be decided without looking at most elements.
- Forgetting the zero-rotation case, where the whole array is already sorted.
Interview questions
Quick revision
- Rotated sorted = two sorted runs; at any mid, one half is sorted.
- Left half sorted if nums[lo] <= nums[mid] (use <=).
- Search: if target inside the sorted half's range go there, else go to the other half.
- Minimum: if nums[mid] > nums[hi] then lo = mid + 1 else hi = mid.
- Rotation count = index of the minimum.
- Duplicates: shrink ends when lo, mid and hi values are equal; worst case O(n).
- Edge cases: no rotation, one or two elements, target at the pivot.
Check yourself
1. In [6, 7, 1, 2, 3, 4, 5] with lo = 0, hi = 6, mid = 3, which half is sorted?
2. To find the minimum of a rotated array, nums[mid] = 9 and nums[hi] = 4. What do you do?
3. What is the worst-case time of searching a rotated sorted array that may contain duplicates?
4. For [4, 5, 6, 7, 0, 1, 2], how many times was the original sorted array rotated?
Saved on this device. Create a free account to keep it on every device.
Practise this with Sam
A real mock interview, out loud, with an honest scorecard. Free to start.