Problem overview
The method search receives a list of distinct integers, nums, and a number target. The list was sorted in ascending order and then possibly rotated: its first k elements were moved, in the same order, to the end. For example, [0, 1, 2, 4, 5, 6, 7] rotated at k = 3 becomes [4, 5, 6, 7, 0, 1, 2]. The method returns the index of target in the rotated list, or -1 if it is not there.
With nums = [4, 5, 6, 7, 0, 1, 2], the target 0 is at index 4, and the target 3 is missing, so the answer is -1. The lesson asks for O(log n) time and O(1) extra space, which rules out a plain scan with O(n) time and points to binary search.
Approach: find the sorted half, then decide
Ordinary binary search needs the whole list to be sorted. A rotated list is not, since it rises, drops once at the rotation point, and rises again. But it still has a useful property: wherever the rotation point is, at least one of the two halves around middle is sorted. The values drop only once, so the drop falls in at most one half, and the other half rises from end to end.
In a sorted range, two comparisons with its ends tell whether a value can be inside it. So each pass of the loop does this:
- Check
nums[middle]. If it equalstarget, returnmiddle. - Find which half is sorted: the left half is sorted when
nums[left] <= nums[middle]. Otherwise the right half is. - If
targetlies between the ends of the sorted half, keep that half. If not, it can only be in the other half, so keep that one.
Each pass discards half of the window, so the loop runs about log2 n times.
The search for 0 in [4, 5, 6, 7, 0, 1, 2] goes like this. At first left is 0, right is 6 and middle is 3, which holds 7. The left half, 4 to 7, is sorted, and 0 is not in it, so the search moves right. Next the window is indexes 4 to 6 and middle is 5, which holds 1. The left half of this window, the elements 0 and 1, is sorted, and 0 lies in it, so right moves to 4. Finally middle is 4, which holds 0, and the method returns 4. For the target 3, the same steps end with an empty window, and the answer is -1.
Step by step
- Set the window:
left, right = 0, len(nums) - 1. Both ends are inclusive, so the window is every index fromlefttoright. - Loop while
left <= right. When the two are equal, one element is still left to check, which is why the comparison is<=. - Compute
middleasleft + (right - left) // 2, using floor division so it stays a whole number. - Return
middleon a match. This check comes first, so the steps below only decide which half to drop. - Test whether the left half is sorted:
nums[left] <= nums[middle]. The<=covers the case whereleftequalsmiddle: one element counts as sorted. - In a sorted left half, if
nums[left] <= targetandtarget < nums[middle], drop the right half by movingrighttomiddle - 1. The upper comparison is strict becausenums[middle]was already checked. - Otherwise the target can't be in the sorted left half, so move
lefttomiddle + 1. - In the other case, the right half is sorted. If
nums[middle] < targetandtarget <= nums[right], drop the left half by movinglefttomiddle + 1. - Otherwise the target can only be in the left half, so move
righttomiddle - 1. - After the loop the window is empty, which means every index that could hold the target was ruled out. Return
-1.
The solution in Python
class Solution:
def search(self, nums: List[int], target: int) -> int:
left, right = 0, len(nums) - 1
while left <= right:
middle = left + (right - left) // 2
if nums[middle] == target:
return middle
if nums[left] <= nums[middle]:
if nums[left] <= target and target < nums[middle]:
right = middle - 1
else:
left = middle + 1
else:
if nums[middle] < target and target <= nums[right]:
left = middle + 1
else:
right = middle - 1
return -1
The Python details that matter here:
//is floor division. It returns an integer, where/would return a float, and a float can't be used as a list index.left + (right - left) // 2gives the same index as(left + right) // 2. Python integers never overflow, so either form is safe here. The first form is the habit that carries over to languages with fixed-size integers.- Tuple assignment in
left, right = 0, len(nums) - 1sets both variables in one line. - Chained comparisons are available.
nums[left] <= target < nums[middle]would mean the same as the two comparisons joined withand. The lesson's version spells them out. - Negative indices. A negative index counts from the end in Python, so
nums[-1]does not raise an error. The window arithmetic keepsmiddlebetweenleftandright, so the loop never indexes outside it.
Complexity
Time: O(log n). Each pass of the loop either returns or discards at least half of the window, so there are at most about log2 n passes, and each does constant work.
Space: O(1). The method keeps three integers, left, right and middle, and never copies the list.
Edge cases and common mistakes
- A list that was not rotated. With
k = 0the list is plain sorted, the left half is always sorted, and the method behaves as ordinary binary search.[1, 2, 3, 4]with target 3 gives 2. - One element.
[1]with target 1 gives 0, and with target 0 gives-1. - Two elements.
[3, 1]with target 1 gives 1. Heremiddleequalsleft, so the left half is one element. With a strictnums[left] < nums[middle]as the test, that element would not count as sorted and the method would return-1. - The target is the first element.
[5, 1, 3]with target 5 gives 0. - The target is missing. The window shrinks to empty and the method reaches the final
return -1. - Testing the wrong half. Compare the target with the ends of the half that is sorted. The other half has the drop in it, and comparing with its ends proves nothing.
- Distinct values. The test
nums[left] <= nums[middle]relies on the values being distinct. With repeats, it can't always tell which half is sorted.
Testing
nums = [4, 5, 6, 7, 0, 1, 2],target = 0gives4.nums = [4, 5, 6, 7, 0, 1, 2],target = 3gives-1.nums = [6, 7, 1, 2, 3, 4, 5],target = 7gives1.nums = [3, 1],target = 1gives1.nums = [1],target = 0gives-1.
