Shifted Search
Given a shifted array of sorted unique integers, write a function findTargetIndex that returns the index of a target value.
You are given an array of sorted integers that has been shifted by an unknown number of spots. For example:
- Original array:
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9] - Shifted array:
[3, 4, 5, 6, 7, 8, 9, 0, 1, 2]
It is the same values in the same order but with the array rotated.
You can assume all the numbers in the array are unique.
If the number doesn't exist in the array, you should return -1.
Breakdown
Approach and test strategy
Binary-search decisions in a rotated ordered array
Read the approach, boundary cases, and complexity
At each midpoint, identify the ordered half of the current interval. Compare the target with that half's endpoints to decide whether it can contain the answer, then discard the other half. Return minus one when no position matches. The usual logarithmic argument relies on the ordering and uniqueness assumptions; repeated equal endpoints can require a different ambiguity policy.
Cases to check
- Check empty input and a singleton with and without a match.
- Place the target before and after the rotation boundary.
- Test the first position, last position, and an absent value.
Cost model
Under the distinct-value rotated-order contract, each step halves the candidate interval for O(log n) time. Iterative boundary state is O(1) auxiliary space.
Programming languages for this lesson
Starter code and reference implementations are available in:
The editor shows which of these languages can run on this deployment.
Validate My Answer
Ensure you have handled both cases where the target exists and doesn't exist in the input array.
Since the array is mostly sorted, you can still use a modified version of binary search to get O(log n) time.
Shifted Search
Given a shifted array of sorted unique integers, write a function findTargetIndex that returns the index of a target value.
You are given an array of sorted integers that has been shifted by an unknown number of spots. For example:
- Original array:
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9] - Shifted array:
[3, 4, 5, 6, 7, 8, 9, 0, 1, 2]
It is the same values in the same order but with the array rotated.
You can assume all the numbers in the array are unique.
If the number doesn't exist in the array, you should return -1.