Given a sorted array that has been rotated at some pivot (e.g., [4,5,6,7,0,1,2] was originally [0,1,2,4,5,6,7]), search for a target value and return its index. Return -1 if not found. All values are unique.
For example, given nums = [4, 5, 6, 7, 0, 1, 2] and target = 0, the output is 4.
Explain how you modify binary search to handle the rotation, how you determine which half is sorted, and analyze complexity.
How to approach it
- Hint 1
In a rotated sorted array, at least one half (left or right of mid) is always sorted.
- Hint 2
Compare nums[mid] with nums[left] to determine which half is sorted.
- Hint 3
If the target falls within the sorted half's range, search there. Otherwise, search the other half.
Ready to answer it out loud?
Record your answer in 1:30 and Preptile scores it 1–10 with specifics — what landed, what you skipped, and what to say next time.
Practising needs an invite code. Join the waitlist and we’ll send you one.