mediumBinary SearchPure DSA~25 min
Search A Rotated Sorted Ring
A sorted array of distinct shard keys was rotated at an unknown pivot during a rebalance. Locate a target key in O(log n) without un-rotating the array.
Problem
Given an integer array nums that was originally sorted ascending and then rotated at an unknown pivot, plus a target value, return the index of target, or -1 if absent. All values are distinct. Run in O(log n).
Input
A rotated sorted integer array nums and an integer target.
Output
The index of target, or -1.
Constraints
- 1 ≤ n ≤ 5000
- -1e4 ≤ nums[i], target ≤ 1e4
- All values distinct.
Examples
Example 1
Input
nums=[4,5,6,7,0,1,2] target=0
Output
4
0 sits at index 4 in the rotated array.
Example 2
Input
nums=[4,5,6,7,0,1,2] target=3
Output
-1
3 is not present.