The challenge
Find the target’s index in an ascending array rotated at an unknown pivot, or return −1.
All values are distinct. Rotation may be zero; empty input returns −1.
Example
[4, 5, 6, 7, 0, 1, 2], target = 0 → 4.
Use the walkthrough below to inspect the input and each state change.
See Rotated search, 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
- 6
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 = 6Recorded result so far
Not resolved
View exact input
Input: [4,5,6,7,0,1,2] · target = 0
Put it into code
At least one half is sorted. Check whether the target lies within that half’s endpoints before choosing where to continue.
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]:
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]) {
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;
}