The problem
A sorted list was rotated at an unknown point. Given a target, return its position or −1, in O(log n) time.
Input: nums = [4, 5, 6, 7, 0, 1, 2], target = 0 Output: 4
Picture it
Same turned clock face. When we cut at the middle, at least one half is still perfectly sorted (no drop inside it). We check that sorted half: if the target lies within its smallest and largest number, search there; otherwise search the other half.
How to recognise it
- The list is sorted, then rotated at an unknown point, and you must find a position in O(log n).
- Cut a rotated list anywhere and at least one half is fully in order. For an ordered half you can tell, from its two ends, whether the target could be inside it.
- So each step can still throw away half the range, even though the whole list is not sorted.
- The values are distinct, which is what makes the "which half is in order" test reliable.
Start with brute force
Scan every position.
def search_brute(a, t):
for i, x in enumerate(a):
if x == t:
return i
return -1
Time is O(n) and space is O(1). LeetCode allows at most 5,000 numbers, so the scan is not slow in practice, but the problem demands O(log n), which is about 13 comparisons for 5,000 numbers. Another option is to find the minimum first (as in LeetCode 153) and binary search the correct run: that is O(log n) too, but takes two searches.
From brute force to the idea
- Find the waste. The scan ignores the fact that each of the two runs is sorted.
- Find the ordered half. Look at
a[lo],a[mid]anda[hi]. Ifa[lo] <= a[mid], the left halflo..midcontains no drop, so it is in order. Otherwise the drop is in the left half, which meansmid..hiis in order. - Use
<=, not<. When only one or two items are left,locan equalmid. A one-item half is in order, and<=says so. - Ask whether the target is inside the ordered half. For an ordered left half, the target is there exactly when
a[lo] <= t < a[mid](the caset == a[mid]was already checked). If so,hi = mid - 1; if not, it can only be on the right, solo = mid + 1. - Mirror it for the right half. If
a[mid] < t <= a[hi], move right withlo = mid + 1; otherwise move left withhi = mid - 1. - Stop when the range is empty. As in plain binary search, the loop runs
while lo <= hiand returns −1 when nothing is left.
This is the key idea: one half is always sorted, and a sorted half can tell you in O(1) whether the target is inside it.
The key idea
At every step one half is sorted. Test whether the target is inside that sorted range to choose a side.
Python solution
def search(a, t):
lo, hi = 0, len(a) - 1
while lo <= hi:
mid = (lo + hi) // 2
if a[mid] == t:
return mid
if a[lo] <= a[mid]: # left half is in order
if a[lo] <= t < a[mid]: hi = mid - 1
else: lo = mid + 1
else: # right half is in order
if a[mid] < t <= a[hi]: lo = mid + 1
else: hi = mid - 1
return -1In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.
Complexity
| Approach | Time | Space |
|---|---|---|
| Brute force | O(n): checks every position | O(1) |
| One-pass binary search (shown code) | O(log n): each step discards about half of lo..hi | O(1): three indices |
Edge cases
- The example (target 0): returns 4; target 3 returns −1.
- One number (
[1]): returns 0 for target 1 and −1 for target 0. - Two numbers, rotated (
[3, 1], target 1):mid == lo, the<=marks the one-item left half as ordered, the target is not in it, so the search moves right and returns 1. - Not rotated (
[1, 2, 3, 4], target 4): the left half is always ordered and the search behaves like plain binary search; returns 3. - Empty list:
histarts at −1, returns −1. - Duplicates: the shown code assumes distinct values. For
[1, 0, 1, 1, 1]and target 0 it returns −1, becausea[lo] <= a[mid]is true even though the left half contains the drop. See the exercise below.
Common mistakes
- Writing
a[lo] < a[mid]. Whenlo == midthis calls a one-item half unordered, and[3, 1]with target 1 returns −1. - Testing only one end, as in
t < a[mid], to decide to go left. In a rotated list a smaller target can be on the right: searching the example for 0 returns −1. - Applying this code to a list with repeats. It gives wrong answers without crashing.
Now values may repeat (LeetCode 81), and you only need to return whether the target is present. For [2, 5, 6, 0, 0, 1, 2], target 0 gives True and target 3 gives False. Describe your approach, then write it if you like.
Compare with our answer
The only new problem is when a[lo] == a[mid] == a[hi]: you cannot tell which half is ordered. Neither end is the target (since a[mid] is not), so shrink both ends by one and look again. Otherwise use the same logic as before.
def search_dups(a, t):
lo, hi = 0, len(a) - 1
while lo <= hi:
mid = (lo + hi) // 2
if a[mid] == t:
return True
if a[lo] == a[mid] == a[hi]: # cannot tell which half is sorted
lo, hi = lo + 1, hi - 1
elif a[lo] <= a[mid]:
if a[lo] <= t < a[mid]: hi = mid - 1
else: lo = mid + 1
else:
if a[mid] < t <= a[hi]: lo = mid + 1
else: hi = mid - 1
return False
search_dups([1, 0, 1, 1, 1], 0) is True. The worst case is O(n), for example a list of 1s with a single 0.
A strong answer mentions: exactly which case is ambiguous, why dropping both ends is safe, and that the worst case becomes O(n).
1. A circular buffer holds sorted message IDs, but the oldest entry is somewhere in the middle. You must find the slot of a given ID quickly. Which approach fits best?
The buffer is a rotated sorted list, so the one-pass rotated search is O(log n). Plain binary search assumes one run, and a sorted copy loses the original slot numbers and costs O(n log n).
2. Why can the shown code decide which half to keep with a single range check?
In a sorted range, a[lo] <= t < a[mid] holds exactly when t could be inside it. If it fails, t can only be in the other half. Which half is sorted varies from step to step.
3. A learner writes if a[lo] < a[mid]: instead of <=. Which call now gives a wrong answer?
In [3, 1], lo == mid, so < wrongly treats the right half as ordered; 3 < 1 fails and the search moves left, returning −1. In the other calls the strict test either never meets lo == mid at a deciding moment or still picks the right side.
Score 60% or more and the lesson is marked complete.