Search in Rotated Sorted Array
A list of distinct integers was sorted in increasing order and then rotated: some number of elements, possibly zero, were taken from the front and moved to the back in the same order. For example, [2, 5, 8, 11, 15, 19, 23] rotated by 4 becomes [15, 19, 23, 2, 5, 8, 11]. You get the rotated list nums and an integer target. Return the index of target in nums, counting from 0, or -1 if it is not there, in O(log n) time.
Function
- numsinteger-array
- the rotated sorted list of distinct integers
- targetinteger
- the value to look for
- Returnsinteger
- the index of target in nums, or -1 if it is missing
Constraints
1 ≤ nums.length ≤ 5000-104 ≤ nums[i], target ≤ 104- All values in
numsare distinct. numsis an increasing list rotated by somekwith0 ≤ k < nums.length;k = 0leaves it unrotated.
Examples
- Input
- nums = [15, 19, 23, 2, 5, 8, 11]target = 5
- Output
- 4
- Explanation
- 5 sits at index 4. The first middle, index 3, holds 2, so the right half
[2, 5, 8, 11]is the sorted one, and 5 lies between 2 and 11. The next middle, index 5, holds 8; the sorted left part[5, 8]holds 5, which leads to index 4.
- Input
- nums = [40, 50, 60, 70, 10, 20, 30]target = 65
- Output
- -1
- Explanation
- 65 would belong between 60 and 70, and no element holds it. The first middle, 70 at index 3, puts 65 inside the sorted left part
[40, 50, 60, 70]. The range shrinks inside that run until it is empty, so the function returns-1.
- Input
- nums = [8, 13, 21, 1, 3, 5]target = 13
- Output
- 1
- Explanation
- The first middle, index 2, holds 21. The left part
[8, 13, 21]is sorted and 13 lies between 8 and 21, so the whole right part is dropped. The search then finds 13 at index 1.
+23 hidden tests on Submit
Follow-up
If nums may contain duplicates, no algorithm can promise O(log n). Can you prove it? Build a rotated list of 1s with a single 0 hidden in it, where any search for 0 has to read every element.
Hints
Open them one at a time. Each one gives away a little more.
Pick any middle index and look at the two halves on either side of it. The rotation created one place where the values go down, from the largest to the smallest. Can both halves contain that drop?
At least one half is always sorted, and comparing
nums[lo]withnums[mid]tells you which one. For a sorted half you can check in one step whethertargetlies between its first and last value.Keep
loandhiaround the part that could still holdtarget. On each step, if the sorted half's value range containstarget, keep that half; otherwise keep the other one. Stop when you findtargetor the range is empty.
Solution
A rotated sorted list is two sorted runs placed one after the other: [15, 19, 23] and then [2, 5, 8, 11]. Plain binary search fails on it, because comparing target with the middle value no longer tells you which side holds target. The fix rests on one fact: wherever you cut the list, at least one of the two halves is fully sorted, and for a sorted half you can tell in one comparison whether target can be inside it.
Scan every element
Intuition
Check every index in order and return the first one whose value equals target. If the loop ends without a match, return -1. The values are distinct, so the first match is the only one, and the scan is correct for any list, rotated or not.
It ignores everything the problem tells you. The list is made of two sorted runs, yet the scan reads up to all 5000 elements, where a binary search needs about 13 comparisons. The gap grows with the input: a million elements cost a million comparisons against about 20. The task asks for O(log n), so this is the baseline to improve on, not the answer.
Algorithm
- For each index
ifrom 0 ton-1, comparenums[i]withtarget. - If they are equal, return
i. - After the loop, return
-1.
def search(nums, target):
for i, value in enumerate(nums):
if value == target:
return i
return -1Find the rotation point, then binary search
Intuition
The rotated list is two sorted runs, and the second one starts at the smallest value. Call its index k. Once you know k, the problem turns into plain binary search: nums[k..n-1] is sorted and holds the values from nums[k] to nums[n-1], and nums[0..k-1] is sorted and holds everything larger. One comparison of target with nums[k] and nums[n-1] picks the run to search.
To find k, binary search on the drop. Compare the middle value with the last value of the range, nums[hi]. If nums[mid] > nums[hi], the values go down somewhere after mid, so the smallest value is to its right: set lo = mid + 1. Otherwise nums[mid..hi] climbs without a drop, so the smallest value is at mid or before it: set hi = mid, keeping mid in range. When lo meets hi, that index is k.
Trace the first example, [15, 19, 23, 2, 5, 8, 11] with target = 5. The middle 2 is not above 11, so hi becomes 3; then 19 is above 2, so lo becomes 2; then 23 is above 2, so lo becomes 3, and k = 3. Since 5 lies between nums[3] = 2 and nums[6] = 11, search indexes 3 to 6, where binary search finds 5 at index 4. Two binary searches cost about 2 log2 n steps.
Algorithm
- Set
lo = 0andhi = n-1. Whilelo < hi, computemid; ifnums[mid] > nums[hi]setlo = mid + 1, otherwise sethi = mid. - Call the final index
k: it holds the smallest value. - If
nums[k] ≤ target ≤ nums[n-1], search indexeskton-1; otherwise search indexes 0 tok-1. - Run plain binary search on that range and return the index of
target, or-1if the range empties.
def search(nums, target):
n = len(nums)
# 1. Find k, the index of the smallest value, where the second run starts.
lo, hi = 0, n - 1
while lo < hi:
mid = (lo + hi) // 2
if nums[mid] > nums[hi]:
lo = mid + 1 # the drop is right of mid
else:
hi = mid # mid is in the low run: the minimum is at mid or left of it
k = lo
# 2. nums[k..n-1] and nums[0..k-1] are sorted: search the one whose range holds target.
if nums[k] <= target <= nums[n - 1]:
lo, hi = k, n - 1
else:
lo, hi = 0, k - 1
while lo <= hi:
mid = (lo + hi) // 2
if nums[mid] == target:
return mid
if nums[mid] < target:
lo = mid + 1
else:
hi = mid - 1
return -1One binary search on the sorted half
Intuition
You do not need to know where the rotation point is. Keep the usual promise of binary search: if target is in the list, its index lies between lo and hi. Look at the middle index mid. The values go down only once in the whole list, so that drop is in at most one of the two halves around mid, and the other half is sorted.
Find the sorted half with one comparison. If nums[lo] ≤ nums[mid], the left half nums[lo..mid] has no drop and is sorted. Since you already know nums[mid] is not target, target can be in that half only if nums[lo] ≤ target < nums[mid]. If so, set hi = mid - 1; if not, target can only be in the other half, so set lo = mid + 1. When nums[lo] > nums[mid], the drop is on the left, the right half nums[mid..hi] is sorted, and the mirror test nums[mid] < target ≤ nums[hi] decides. You never reason about the unsorted half directly: it gets target exactly when the sorted half cannot.
Trace the first example, [15, 19, 23, 2, 5, 8, 11] with target = 5. The range 0 to 6 has middle 3, value 2. Since 15 is above 2, the right half [2, 5, 8, 11] is sorted, and 5 lies in it, so lo becomes 4. The range 4 to 6 has middle 5, value 8. Now nums[4] = 5 ≤ 8, the left half [5, 8] is sorted and holds 5, so hi becomes 4. Index 4 holds 5: return 4.
Every step halves the range, as in plain binary search, so the loop runs at most about log2(n) + 1 times: 13 steps for 5000 elements, with two indexes of extra memory.
Algorithm
- Set
lo = 0andhi = n-1. - While
lo ≤ hi, computemid. Ifnums[mid]equalstarget, returnmid. - If
nums[lo] ≤ nums[mid], the left half is sorted: ifnums[lo] ≤ target < nums[mid]sethi = mid - 1, otherwise setlo = mid + 1. - Otherwise the right half is sorted: if
nums[mid] < target ≤ nums[hi]setlo = mid + 1, otherwise sethi = mid - 1. - When the loop ends, return
-1.
def search(nums, target):
lo, hi = 0, len(nums) - 1 # target, if present, sits in nums[lo..hi]
while lo <= hi:
mid = (lo + hi) // 2
if nums[mid] == target:
return mid
if nums[lo] <= nums[mid]:
# nums[lo..mid] is sorted: target is in it only if it fits its range
if nums[lo] <= target < nums[mid]:
hi = mid - 1
else:
lo = mid + 1
else:
# nums[mid..hi] is sorted
if nums[mid] < target <= nums[hi]:
lo = mid + 1
else:
hi = mid - 1
return -1
Pitfalls and edge cases
The one-pass search is short, and nearly every bug sits in a comparison operator.
- Writing
nums[lo] < nums[mid]instead of≤. When two elements are left,midequalslo, and the left half is one element, which is sorted. With the strict test,[9, 4]andtarget = 4treat[9, 4]as the sorted right half, find 4 outside the range from 9 to 4, and return-1. - Comparing
targetwithnums[mid]first, as in plain binary search. In[15, 19, 23, 2, 5, 8, 11]withtarget = 19, the middle value 2 is smaller than 19, so the search moves right and never sees index 1. - Testing only one end of the sorted half. In
[40, 50, 60, 70, 80, 10, 20]withtarget = 80, the middle value is 70 and the left half[40, 50, 60, 70]is sorted. The checktarget ≥ nums[lo]alone sends the search left, because 80 is above 40, but 80 is also above 70, so it sits in the right half. Check both ends. - Forgetting the unrotated case in the two-step approach. When
k = 0, the second run is empty and its range is0to-1. That is fine with signed indexes, but with unsigned ones (Rust'susize)k - 1underflows, which is why the Rust code uses half-open ranges. - Returning the position itself in Lua and R. Their lists start at 1, so subtract 1 before returning.
Frequently asked questions4
What is the time complexity of searching a rotated sorted array?
O(log n) time and O(1) extra space. Each step keeps one half of the current range, the same as plain binary search, so a list of 5000 elements needs at most 13 steps. The two-step version that finds the rotation point first is also O(log n), with about twice as many steps.
How do you know which half of a rotated array is sorted?
Compare nums[lo] with nums[mid]. The values go down only once in the whole list. If nums[lo] ≤ nums[mid], that drop is not between lo and mid, so the left half is sorted. Otherwise the drop is in the left half, which means the right half, from mid to hi, has none and is sorted.
Does the algorithm work when the array contains duplicates?
Not as written. In [1, 0, 1, 1, 1], nums[lo], nums[mid] and nums[hi] are all 1, so neither half can be proven sorted. The usual fix is to move lo forward by one when nums[lo], nums[mid] and nums[hi] are equal, which keeps the answer correct but makes the worst case O(n).
Should you find the rotation point first or search in one pass?
Both run in O(log n). Finding the index of the minimum first splits the problem into two plain binary searches, so each part reuses code you already trust. The one-pass search does the same job in a single loop with fewer steps, and it is the version most interviewers expect.
Similar problems
Problems that use the same ideas. Solving two or three of them is what makes a pattern stick.
Python
def search(nums, target):
# Write code hereCase 1
Case 2
Case 3
Input
nums = [15, 19, 23, 2, 5, 8, 11] target = 5
Expected
4