Rotated Sorted Arrays and Finding a Peak
20 min · Intermediate
Need help? Ask a tutor on WhatsApp (opens in a new tab)Real data is often only almost sorted: a log that wrapped around, or a list that starts in the middle. Binary search still works when each probe can tell you which half to throw away.
What rotation does
A rotated sorted array is a sorted list whose front part was moved to the back, such as [30, 40, 50, 10, 20]. It has one drop, and the smallest value sits right after it.
A sorted list rotated by two places turns [10, 20, 30, 40, 50] into [30, 40, 50, 10, 20]. It is two sorted runs with one drop between them. Around any middle item, at least one half is still sorted.
Example 1 · Brute force: scan for the smallest value
stock = [30, 40, 50, 10, 20]smallest = min(stock)rotations = stock.index(smallest)print(smallest, rotations)10 3
What this code does
- min reads every item, so this is O(n). The position of the smallest value shows where the sorted order starts.
- Binary search uses the rotated shape to find the same position in O(log n).
Find the smallest value
Compare the middle item with the last item of the window. If the middle is larger, the drop is to its right. Otherwise the middle is in the second run, so the smallest value is at mid or to its left.
def find_min(items): lo, hi = 0, len(items) - 1 while lo < hi: mid = (lo + hi) // 2 if items[mid] > items[hi]: lo = mid + 1 else: hi = mid return lo
print(find_min([30, 40, 50, 10, 20]))3
Example 2 · Smallest value on four shapes
def find_min(items): lo, hi = 0, len(items) - 1 while lo < hi: mid = (lo + hi) // 2 if items[mid] > items[hi]: lo = mid + 1 else: hi = mid return lo
for stock in ([30, 40, 50, 10, 20], [10, 20, 30, 40, 50], [20, 10], [7]): spot = find_min(stock) print(stock, "-> index", spot, "value", stock[spot])[30, 40, 50, 10, 20] -> index 3 value 10 [10, 20, 30, 40, 50] -> index 0 value 10 [20, 10] -> index 1 value 10 [7] -> index 0 value 7
What this code does
- A list that was not rotated gives position 0, a list of one item gives 0, and [20, 10] has its drop in the middle.
- Time is O(log n) and extra space is O(1).
Example 3 · Duplicates: shrink the window by one
def find_min_with_duplicates(items): lo, hi = 0, len(items) - 1 while lo < hi: mid = (lo + hi) // 2 if items[mid] > items[hi]: lo = mid + 1 elif items[mid] < items[hi]: hi = mid else: hi -= 1 return items[lo]
print(find_min_with_duplicates([3, 3, 1, 3]))print(find_min_with_duplicates([2, 2, 2, 0, 1, 2]))print(find_min_with_duplicates([1, 1, 1, 1]))1 0 1
What this code does
- When the middle equals the right end, the drop could be on either side, so only the right end can be dropped safely.
- On a list of equal values this takes O(n) steps, so the worst case is no better than a scan.
The function returns the position of the smallest value. Comparing with items[hi] works because the right end always belongs to the second run, or the whole window is sorted.
Search a target in a rotated list
Compare items[lo] with items[mid]: if it is not larger, the left half is sorted. Check whether the target lies inside that sorted half. If yes keep it, otherwise keep the other half.
items = [30, 40, 50, 10, 20]lo, hi = 0, 4mid = (lo + hi) // 2print("left half sorted:", items[lo] <= items[mid])print("40 in left half:", items[lo] <= 40 < items[mid])print("10 in left half:", items[lo] <= 10 < items[mid])left half sorted: True 40 in left half: True 10 in left half: False
Example 4 · Search a target in a rotated list
def search_rotated(items, target): lo, hi = 0, len(items) - 1 while lo <= hi: mid = (lo + hi) // 2 if items[mid] == target: return mid if items[lo] <= items[mid]: if items[lo] <= target < items[mid]: hi = mid - 1 else: lo = mid + 1 else: if items[mid] < target <= items[hi]: lo = mid + 1 else: hi = mid - 1 return -1
stock = [30, 40, 50, 10, 20]for target in [10, 40, 20, 35]: print(target, "->", search_rotated(stock, target))10 -> 3 40 -> 1 20 -> 4 35 -> -1
What this code does
- Each round finds the sorted half, tests whether the target belongs in it, and keeps one half. That is O(log n).
- 35 is not in the list, so the window runs out and the result is -1.
A sorted half has a clear range, so one comparison tells whether the target can be inside it. The full loop applies this test every round.
Find a peak
A peak element is an item larger than both neighbours. An item at either end only needs to be larger than its one neighbour. A list can have several peaks.
A peak is an item larger than its neighbours. Compare the middle with the next item. If the values still rise, a peak lies to the right. Otherwise mid is a peak or a peak lies to the left.
def find_peak(items): lo, hi = 0, len(items) - 1 while lo < hi: mid = (lo + hi) // 2 if items[mid] < items[mid + 1]: lo = mid + 1 else: hi = mid return lo
print(find_peak([1, 3, 7, 12, 9, 4]))3
Example 5 · A list with two peaks
def find_peak(items): lo, hi = 0, len(items) - 1 while lo < hi: mid = (lo + hi) // 2 if items[mid] < items[mid + 1]: lo = mid + 1 else: hi = mid return lo
sales = [1, 5, 2, 8, 3]spot = find_peak(sales)print(spot, sales[spot])3 8
What this code does
- The list has peaks at positions 1 and 3. Binary search returns one of them, and any peak is a correct answer.
- Ask the interviewer whether any peak is acceptable. If the highest is needed, binary search is not enough.
Example 6 · Mountain list: the highest point
def find_peak(items): lo, hi = 0, len(items) - 1 while lo < hi: mid = (lo + hi) // 2 if items[mid] < items[mid + 1]: lo = mid + 1 else: hi = mid return lo
visitors = [2, 6, 9, 12, 8, 3]spot = find_peak(visitors)print(spot, visitors[spot])print(visitors.index(max(visitors)))3 12 3
What this code does
- In a list that rises and then falls there is exactly one peak, so the binary search finds the maximum.
- The last line is the O(n) brute force. Both give the same position.
Going uphill can never lead off the list: either the values keep rising to the end, or they fall somewhere, and the top before the fall is a peak. The list does not have to be sorted.
Next step
Check your understanding
11 quick questions