Rotated / mountain search

37 s · title card, the worked example step by step, then a recap. The captions carry the explanation; there is no narration. Download the MP4.

01The intuition

Start with what you would do by hand

A sorted list was cut somewhere and the two pieces swapped: 4, 5, 6, 7, 0, 1, 2. It was 0, 1, 2, 4, 5, 6, 7 before. Find 0.

By hand you scan: 4, 5, 6, 7, 0, five looks. For a million numbers rotated, up to a million looks. Plain binary search seems broken: the middle is 7, the target 0 is smaller, so we would go left to 4, 5, 6 and miss it.

Look more carefully at the list around the middle. The left half 4, 5, 6, 7 is perfectly sorted. The right half 0, 1, 2 is also sorted. The rotation point, where 7 drops to 0, lies in exactly one of the two halves, so the other half is sorted normally. And in a sorted half we can tell with two comparisons whether the target belongs inside it.

Build the structure, one piece at a time

Piece 1: the range. lo = 0, hi = 6, mid = 3. nums[mid] = 7.

Piece 2: which half is sorted? Compare the ends. If nums[lo] ≤ nums[mid], the left half is sorted (4 ≤ 7, yes). Otherwise the right half is sorted.

Piece 3: is the target inside the sorted half? For a sorted left half, the target is inside it when nums[lo] ≤ target < nums[mid]. Is 4 ≤ 0 < 7? No. So the target must be in the other half: lo = mid + 1 = 4.

Piece 4: repeat.

Three looks instead of five, and about twenty for a million numbers.

Why it is correct

The invariant: the target, if present, is inside [lo, hi].

The key claim is that one of the two halves is sorted. A rotated sorted list has exactly one "drop", where a value is followed by a smaller one. The drop is either in the left half or in the right half, not both, so the other half has no drop and is sorted. The test nums[lo] ≤ nums[mid] detects a sorted left half: if the drop were inside the left half, the values would go up, drop, and come back up below nums[lo], so nums[mid] < nums[lo].

Once we know a half is sorted, deciding membership is exact: a value is inside a sorted range of numbers between nums[lo] and nums[mid] if and only if nums[lo] ≤ target < nums[mid]. If the target is not in the sorted half, it must be in the other half, and we keep that. Either way the half we discard cannot contain the target, so the invariant survives.

The same idea solves "find the minimum of a rotated array": compare nums[mid] with nums[hi]; if nums[mid] > nums[hi] the drop is to the right, else it is at mid or to the left. And "find a peak element" is the mountain version: if nums[mid] < nums[mid + 1] the slope goes up, so a peak exists to the right; otherwise a peak exists at mid or to the left.

Why it is fast

Every step still discards half of the range, with at most three comparisons instead of one.

steps ≤ ⌈log₂ n⌉, so O(log n) time

When duplicates are allowed, nums[lo] = nums[mid] = nums[hi] can hide which half is sorted; then you shrink both ends by one and continue, which can degrade to O(n) on a list of equal values but is still correct.

How to recognise it in an interview

The cues are "rotated sorted array", "pivot", "mountain array" (goes up then down), "find peak", "minimum in rotated array". The input is almost sorted in a way that preserves one sorted side at every split. Say: "At any midpoint one half is sorted, so I check whether the target lies in the sorted half and discard the other."

Search in Rotated Sorted Array is the example above. Find Minimum in Rotated Sorted Array compares mid with hi to locate the drop. Find Peak Element uses the slope at mid to decide which side must hold a peak.

02The idea in one line

One half is always sorted: decide which, then whether the target lives there.

Reach for it when: Rotated sorted array search, minimum in rotated array, peak finding.

Cost: O(log n) time.

03The walk-through, step by step

The video works one example: Search 0 in [4,5,6,7,0,1,2]. These are its captions in order, so you can follow without the video or check a step you missed.

1. One half of [lo, hi] is always sorted; decide which, then where the target is
2. mid = 3, nums[mid] = 7
3. nums[0]=4 ≤ nums[3]=7: the left half is sorted
4. 0 is not in the sorted left half: go right, lo = 4
5. mid = 5, nums[mid] = 1
6. nums[4]=0 ≤ nums[5]=1: the left half is sorted
7. 0 lies in [0, 1): keep the left, hi = 4
8. mid = 4, nums[mid] = 0
9. Found 0 at index 4
10. Still halving every step: O(log n)

04Asked at Google

8 Google-tagged LeetCode problems use this pattern. Frequency is LeetCode's Google-tag score (higher means reported more often); "last 6 months" marks problems reported in the most recent window of the export.

05Related patterns

Other patterns in Binary Search: Classic binary search, First true (predicate boundary), Binary search on the answer, Partition two sorted arrays.