The challenge
Find any matching target index in a rotated nondecreasing array, or return −1.
Duplicates allowed. Any matching index is valid; empty input returns −1.
Example
[1, 0, 1, 1, 1], target = 0 → 1.
Use the walkthrough below to inspect the input and each state change.
See Duplicate-aware rotation, step by step
Inspect the comparison, the invariant, and the next boundary.
Inclusive candidate indicestarget = 0
Current comparisonResolved positionNumbers below = indices
- Left
- 0
- Middle
- —
- Right
- 4
Step 01 / 5
Start with the candidate indices
The retained interval contains the answer whenever it exists. Watch why each comparison can discard one side.
left = 0; right = 4Recorded result so far
Not resolved
View exact input
Input: [1,0,1,1,1] · target = 0
Put it into code
Use rotated search, but remove both endpoints when left, middle, and right all have the same value after a failed equality check.
Indices are zero-based. C++ uses C++17 or later.
def rotated_search(nums, target):
left, right = 0, len(nums) - 1
while left <= right:
mid = left + (right - left) // 2
if nums[mid] == target:
return mid
if nums[left] == nums[mid] == nums[right]:
left += 1
right -= 1
continue
if nums[left] <= nums[mid]:
if nums[left] <= target < nums[mid]:
right = mid - 1
else:
left = mid + 1
else:
if nums[mid] < target <= nums[right]:
left = mid + 1
else:
right = mid - 1
return -1#include <vector>
int rotated_search(const std::vector<int>& nums, int target) {
int left = 0, right = static_cast<int>(nums.size()) - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) return mid;
if (nums[left] == nums[mid] && nums[mid] == nums[right]) {
++left; --right;
continue;
}
if (nums[left] <= nums[mid]) {
if (nums[left] <= target && target < nums[mid]) right = mid - 1;
else left = mid + 1;
} else {
if (nums[mid] < target && target <= nums[right]) left = mid + 1;
else right = mid - 1;
}
}
return -1;
}