Example 1
ready- Input
nums = [ 4, 5, 6, 7, 0, 1, 2 ] target = 0- Expected
4- Why
- 0 is present in the low-value half
Search in Rotated Sorted Array
35 min · search()mediumOpen in LeetCode #33 ↗
The sorted array has a bend in it. Your search needs to see around that corner.
You're given a strictly increasing array that was rotated, meaning a prefix — a
block from the front — may have been moved to the end while both pieces kept their
internal order. Given target, return its zero-based index, or -1 when it isn't present.
The array may have been rotated zero times, so ordinary sorted input is valid too.
A few ground rules:
- All values are distinct, so a present target has one index.
- You need to search the rotated order as given; don't sort a copy.
- Aim to discard half of the remaining indices after each comparison.
Constraints
1 <= nums.length <= 100_000-1_000_000_000 <= nums[i], target <= 1_000_000_000- All values are distinct.
numsis a rotation of a strictly increasing array.
Hints
One half is still clean
For any middle index, at least one side of the current interval is normally sorted.
Compare nums[left], nums[middle], and nums[right] to identify it.
Ask whether target fits
Once you know which half is sorted, check whether target falls inside that half's
value range. Keep that half if it does; discard it if it doesn't.
Use inclusive boundaries carefully
In the sorted left half, test nums[left] <= target < nums[middle]. The mirrored
right-half test is nums[middle] < target <= nums[right].
Follow-up
How does the reasoning change when duplicate values can make both ends equal to the middle?
Visible cases
Examples
Example 2
ready- Input
nums = [ 4, 5, 6, 7, 0, 1, 2 ] target = 6- Expected
2- Why
- 6 is present before the rotation seam
Example 3
ready- Input
nums = [ 4, 5, 6, 7, 0, 1, 2 ] target = 3- Expected
-1- Why
- 3 doesn't appear on either side
Interview signal
Asked at
AmazonGoogleMicrosoft
Linear scan
Check each position until you find target.
def search(nums: list[int], target: int) -> int:
for index, value in enumerate(nums):
if value == target:
return index
return -1Time O(n). Space O(1). This works, but the rotated sorted structure does no work for you.
One-pass rotated search
A rotation can split the array into two increasing pieces, but it can't scramble both
halves around middle. At least one half of the current interval is sorted.
If nums[left] <= nums[middle], the left half is sorted. Keep it only when target
lies in [nums[left], nums[middle]); otherwise search right. If the left half isn't
sorted, the right half is, and the same test works in reverse.
def search(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 < nums[middle]:
right = middle - 1
else:
left = middle + 1
else:
if nums[middle] < target <= nums[right]:
left = middle + 1
else:
right = middle - 1
return -1The distinct-values rule is doing real work: it lets nums[left] <= nums[middle]
identify a sorted side without ambiguity.
Time O(log n). Space O(1). Every iteration keeps at most half of the live interval.
Loading editor
Console
ready to runReady to run.
3 cases are queued.
Visible testcase
Case 1
Expected
4
Run: visible + custom · Submit: full suite