Where it runs
1. The problem
In the last two lessons the list was sorted from start to end, low to high. Binary search worked because the middle cell always told you which half held the value you were looking for (the target). Now the list is sorted too, but someone rotated it: it was cut at one point and the two pieces were swapped.
Take [4, 5, 6, 7, 0, 1, 2]. The numbers climb 4, 5, 6, 7, then drop to 0, then climb again 1, 2. This is [0, 1, 2, 4, 5, 6, 7] rotated so that 4 comes first. The numbers are still all different, and inside each piece they still go up. You don't know where the drop is.
You want the index of a value in O(log n), as fast as plain binary search. Going through every cell would take O(n) and would make no use of the order that is still in the list.
2. In plain words
Look for 0 in [4, 5, 6, 7, 0, 1, 2]. The middle holds 7. Left of it are 4, 5, 6, 7: the numbers climb with no drop. So the left half is sorted, and it holds only numbers from 4 to 7. 0 can't be among them. So it is on the right: [0, 1, 2].
Every step works this way. You split the list in half. One of the halves is always in order, with no drop inside. Its first and last numbers tell you which numbers it holds. If the number you want falls in that range, search that half. If not, search the other one. Either way, half the numbers are dropped.
3. The idea
Keep two bounds, lo and hi, and take the middle mid. If nums[mid] equals target, you are done. If not, you have to pick a side. The array is not sorted from start to end, so one comparison of target with the middle is not enough.
The fact to rely on: at any mid, at least one of the two halves is fully sorted, with no drop inside. To find out which, compare nums[lo] with nums[mid]. If nums[lo] <= nums[mid], the left half is sorted. Otherwise the drop is on the left, and the right half is sorted. Now you have one half whose range of values you know exactly. If target falls in it, move into that half. If not, move into the other one.
Trace it on [4, 5, 6, 7, 0, 1, 2], looking for 0:
- Start:
lo = 0,hi = 6,mid = 3,nums[mid] = 7. That is not 0.nums[lo] = 4 <= 7, so the left half4..7is sorted. 0 is not in4..7, so go right:lo = 4. - Now
lo = 4,hi = 6,mid = 5,nums[mid] = 1. That is not 0.nums[lo] = 0 <= 1, so the left half0..1is sorted. 0 is in it, so go left:hi = 4. - Now
lo = 4,hi = 4,mid = 4,nums[4] = 0. A match. Return 4.
4. What it costs
Time: O(log n). As in plain binary search, every step drops half of what is left. Each step adds a couple of comparisons to pick the sorted half. That is O(1), and it doesn't change the number of steps.
Memory: O(1). You keep lo, hi and mid, and none of them grows with the input.
5. Where this shows up
A circular buffer (an array of fixed size that fills up in a circle) records data in order. When it reaches the end, it goes on from the start, and the point where it wrapped is not known in advance. So the stored array is a rotated sorted array, and looking up a value in it works the same way. Another case: reading a ring log by timestamp or record number without going through the whole log. In general this search fits any structure that keeps its data in order but starts at a moving place, when the lookup still has to take O(log n).
searchRotated([7, 8, 9, 1, 2, 3, 4, 5, 6], 9)lo
hi
Find 9 in a sorted array that was cut and swapped. Each of the two pieces is still sorted.
Bars: sorted numbers rotated by 14, so the smallest sits at index 14. Both lanes look for one near the end.
One operation is one element read. Every frame, each lane does the same number of operations, so the slow one falls behind.
O(n)O(log n)
Operations for n numbers, and roughly how long they take at 100 million simple operations a second. An estimate from the same count, not a measurement.
Recognise it
Say these words and it is this pattern
- sorted array rotated at an unknown pivot
- find a target in O(log n)
- no duplicates (or handle them separately)
- find the minimum / the rotation point
- array increases then drops once
Looks similar, isn't
- Binary search (array)
A plain search compares the middle against the target. Here it is compared against a bound first.
- Linear search
A scan handles a rotated array with no reasoning at all. It costs O(n) instead of O(log n).
- Binary search on the answer
There the range is made of candidate answers. Here you are searching real stored values.
- Fast sort (merge / quick)
Sorting restores the order but costs n log n. The rotation already leaves enough order to use.
n up to 1e9 gives O(log n), the same as a plain search. Duplicates push the worst case to O(n).
On LeetCode
Problems on a sorted array that was cut and had its two parts swapped, where you search, find the minimum or find a peak in O(log n). At each step one half is still sorted, and its ends tell you which side to keep.
This is the lesson task, with all values different.
Compare the middle with the right end to tell which side holds the drop.
The same search with repeats, where nums[lo] == nums[mid] forces you to move lo by one.
Halve the range by comparing the middle with its right neighbour.
Your task (Tier 1)
Write the function searchRotated(nums, target).
The list was sorted low to high. Then it was cut at one point and the two parts were swapped. So the numbers climb, drop once, then climb again, like [4, 5, 6, 7, 0, 1, 2]. All numbers are different. Find target and return its position, or -1 if it is not there. Halve the range at every step instead of going through every number.
- Input:
nums, a rotated sorted list of different numbers, andtarget, the number you are looking for. Example:[4, 5, 6, 7, 0, 1, 2]with target0. - Return: the position of
target, or-1if it is not there.
Steps:
- Keep two bounds,
loandhi. Whilelo <= hi, take the middle positionmid. Ifnums[mid]equalstarget, returnmid. - One of the halves around
midis always sorted. Comparenums[lo]withnums[mid]to see which one. - If
targetfalls in the range of values of the sorted half, move into that half. Otherwise move into the other half. If the bounds cross, return-1.
Done when all tests pass:
[4, 5, 6, 7, 0, 1, 2], target0->4(in the second part)[4, 5, 6, 7, 0, 1, 2], target5->1(in the first part)[4, 5, 6, 7, 0, 1, 2], target3->-1(not there)[1, 2, 3, 4, 5], target4->3(not rotated at all)[6, 7, 0, 1, 2, 4, 5], target6->0(right at the cut)[1], target1->0(one number, found)[1], target2->-1(one number, not found)[], target5->-1(empty list, the function must not crash)
Practice
searchRotated
searchRotated(nums, target) -> index of target in the rotated sorted array, or -1
export function searchRotated(nums, target) {
// Your code here. The task is described in the box above the editor.
}
Running as a guest
The tests run right here, no account needed. Your code is kept in this browser only. A free account keeps it on every device, marks the step done and shows where you are in the course.
Hint ladder
Stuck? Reveal one rung at a time, but try it yourself first.