Search in Rotated Sorted Array
A sorted array was turned like a dial. Find a target's index in O(log n) by working out which half is still sorted.
- Binary search on a rotated array
- Find the sorted half
Before this, know: Classic binary search (week 3), Arrays and indexes
Start with a sorted array: the numbers go up from left to right, like
[0, 1, 2, 4, 5, 6, 7]. Now rotate it: take some numbers off the front
and stick them on the back, keeping their order. Moving [0, 1, 2] to the back
gives [4, 5, 6, 7, 0, 1, 2].
You get the rotated array nums and a number target. Return the index
(position, counting from 0) of target, or -1 if it isn’t there.
- 40
- 51
- 62
- 73
- 04
- 15
- 26
The rules that matter:
- All the numbers are different (no duplicates).
- You don’t know how far it was rotated. It might not be rotated at all.
- The problem asks for O(log n) time. That phrase is a loud hint: it means “use binary search”. (O(log n) means: double the array, and the work grows by just one extra step.)
Draw the array as bars and you see two rising ramps with one drop between them:
Here’s the fact the whole solution rests on. Pick any middle index. The drop is on one side of it, so the other side has no drop: it is sorted. And with a sorted stretch, we know exactly which numbers it can contain: everything between its first and last value.
Pause and think
Compare nums[lo] = 6 with nums[mid] = 2. Since 6 > 2, the drop must be in the
left half (6, 7, then down to 1). So the right half 2, 3, 4, 5 is the sorted one.
A sorted run from 2 to 5 can only hold values 2 to 5. 7 is bigger than 5, so 7 can’t be on the right. Throw the right half away and search the left.
Forget about the sorting and look at every number from left to right until we
find the target. We use one pointer i (a variable that holds a position).
Brute force: check every number
nums = [4, 5, 6, 7, 0, 1, 2], target = 0
- 40
- 51
- 62
- 73
- 04
- 15
- 26
- target
- 0
- checks
- 1
- answer
- —
- Checking now
- Already checked
- Target
Check #1: nums[0] = 4, not 0. Move on.
Which line is running?
function search(nums, target) { for (let i = 0; i < nums.length; i++) {Running now: if (nums[i] === target) { return i; } } return -1; // looked everywhere: not there}Brute force: linear scan
function search(nums, target) { for (let i = 0; i < nums.length; i++) { if (nums[i] === target) { return i; } } return -1; // looked everywhere: not there}def search(nums, target): for i in range(len(nums)): if nums[i] == target: return i return -1 # looked everywhere: not thereIt’s correct, but it can look at every element. For 7 numbers that’s up to 7 checks. For 5,000 numbers (LeetCode’s limit) it’s up to 5,000 checks. That is O(n): double the array, double the work. It completely ignores the fact that the array is (almost) sorted.
Binary search would need only about 13 checks for 5,000 numbers, because each check throws away half of what’s left (5,000 → 2,500 → 1,250 → … → 1).
You learned plain binary search in week 3:
keep a range lo..hi, look at the middle, and throw away the half that can’t
contain the target. The only new problem here is “how do I know which half to
throw away when the array isn’t fully sorted?”
Pattern
Binary search on a rotated array
Use it when: the array was sorted and then rotated (shifted around in a circle), and you need O(log n).
Signal words
- “rotated sorted array”
- “sorted then rotated”
- “pivot”
- “O(log n)”
- “distinct values”
- Set
lo = 0andhi = n − 1. The target, if it exists, is somewhere inlo..hi. - While
lo <= hi, computemid = (lo + hi) // 2(rounded down). - If
nums[mid]is the target, returnmid. - If
nums[lo] <= nums[mid], the left halflo..midis sorted. Ifnums[lo] <= target < nums[mid], the target is in it:hi = mid − 1. Otherwiselo = mid + 1. - Else the right half
mid..hiis sorted. Ifnums[mid] < target <= nums[hi], the target is in it:lo = mid + 1. Otherwisehi = mid − 1. - If the loop ends (
lo > hi), the target isn’t there: return−1.
Press Play and watch the shaded window: it marks the half we just proved is sorted. Faded cells are thrown away for good. Try “Right half sorted” to see the other branch, and the edge cases.
Binary search: find the sorted half
nums = [4, 5, 6, 7, 0, 1, 2], target = 0
- 40
- 51
- 62
- 73
- 04
- 15
- 26
- target
- 0
- lo
- 0
- hi
- 6
- mid
- —
- sorted half
- —
- answer
- —
- The half we proved is sorted
- nums[mid]
- Thrown away
- Target
We look for 0. The search range is everything: lo = 0 and hi = 6. The array was sorted, then rotated, so somewhere there may be a "drop" where a big number is followed by a small one.
Which line is running?
function search(nums, target) {Running now: let lo = 0; let hi = nums.length - 1; while (lo <= hi) { const mid = Math.floor((lo + hi) / 2); if (nums[mid] === target) return mid; if (nums[lo] <= nums[mid]) { // Left half [lo..mid] is sorted. if (nums[lo] <= target && target < nums[mid]) { hi = mid - 1; // target is inside the sorted left half } else { lo = mid + 1; // target must be on the right } } else { // Right half [mid..hi] is sorted. if (nums[mid] < target && target <= nums[hi]) { lo = mid + 1; // target is inside the sorted right half } else { hi = mid - 1; // target must be on the left } } } return -1; // the range is empty: target is not in nums}Notice that each step costs only a couple of comparisons, and half of the range disappears every time.
Binary search on the sorted half
function search(nums, target) { let lo = 0; let hi = nums.length - 1; while (lo <= hi) { const mid = Math.floor((lo + hi) / 2); if (nums[mid] === target) return mid; if (nums[lo] <= nums[mid]) { // Left half [lo..mid] is sorted. if (nums[lo] <= target && target < nums[mid]) { hi = mid - 1; // target is inside the sorted left half } else { lo = mid + 1; // target must be on the right } } else { // Right half [mid..hi] is sorted. if (nums[mid] < target && target <= nums[hi]) { lo = mid + 1; // target is inside the sorted right half } else { hi = mid - 1; // target must be on the left } } } return -1; // the range is empty: target is not in nums}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 [lo..mid] is sorted. if nums[lo] <= target < nums[mid]: hi = mid - 1 # target is inside the sorted left half else: lo = mid + 1 # target must be on the right else: # Right half [mid..hi] is sorted. if nums[mid] < target <= nums[hi]: lo = mid + 1 # target is inside the sorted right half else: hi = mid - 1 # target must be on the left return -1 # the range is empty: target is not in numsThe two versions drift by a line here and there (JavaScript sets lo and hi
on two lines, Python returns mid on its own line), so below “JS n / Py m”
gives both line numbers. On LeetCode the Python version lives inside
class Solution as def search(self, nums, target); the body is the same.
- JS 2–3 / Py 2: the search range starts as the whole array.
hiis the last index,n − 1. - JS 4 / Py 3: keep going while the range
lo..histill has at least one number. - JS 5 / Py 4: the middle index.
Math.floorin JS and//in Python round down, somidis always a whole number. - JS 6 / Py 5–6: lucky hit, we’re done.
- JS 7 / Py 7: the key test. If the first number of the range is ≤ the middle
one, nothing drops between them, so
lo..midis sorted. We use<=(not<) because whenlo === midthe “half” is a single number, which counts as sorted. - JS 9 / Py 9: is the target inside the sorted left half? It must be at least
nums[lo]and less thannums[mid](we already know it isn’t equal tonums[mid]). Python can chain the comparison:nums[lo] <= target < nums[mid]. - JS 10 & 12 / Py 10 & 12: shrink the range to the half that can still hold the target.
- JS 16–19 / Py 15–18: the mirror image when the right half
mid..hiis the sorted one: the target must be greater thannums[mid]and at mostnums[hi]. - JS 23 / Py 19: the range became empty, so the target isn’t in the array.
nums = [4, 5, 6, 7, 0, 1, 2], target = 0:
| lo | hi | mid | nums[mid] | sorted half | target in it? | next range |
|---|---|---|---|---|---|---|
| 0 | 6 | 3 | 7 | left: 4..7 | no (0 < 4) | lo = 4 |
| 4 | 6 | 5 | 1 | left: 0..1 | yes (0 ≤ 0 < 1) | hi = 4 |
| 4 | 4 | 4 | 0 | — | found! | return 4 |
The first row (mid = 3, where nums[mid] is 7) is the interesting one: 0 is smaller than everything, so a beginner might
search left. But the left half is the sorted run 4..7, which can’t hold a 0, so
we correctly go right, past the drop.
Brute force
Time
O(n)
Might look at every number once: 5,000 numbers, up to 5,000 checks.
Space
O(1)
Just the index i.
Binary search on the sorted half
Time
O(log n)
Every loop throws away half the range. 5,000 numbers need at most about 13 loops.
Space
O(1)
Only three numbers: lo, mid and hi.
What to say out loud:
- “O(log n) means binary search, but the array isn’t fully sorted, so I need a new rule for which half to drop.”
- “Any mid splits the range in two, and the single drop is in only one of them, so the other half is sorted.”
- “I can check whether the target lies in the sorted half just by comparing with its two ends.”
- “Each step halves the range: O(log n) time, O(1) space.”
- Dry-run a case where the target is on the far side of the drop (like 0 above).
Likely follow-ups:
- “Find the minimum of a rotated array.” That’s Find Minimum in Rotated
Sorted Array (LeetCode 153) from week 3. Same idea: compare
nums[mid]withnums[hi]to see which side the drop (and the minimum) is on. - “What if there are duplicates?” (LeetCode 81) Then
nums[lo] == nums[mid]doesn’t tell you which half is sorted; you shrink by one (lo++), and the worst case becomes O(n).
Related problems:
- Binary search fundamentals in week 3.
- Koko Eating Bananas and Time Based Key-Value Store: two more twists on binary search this week.