391. Search the Turned Shelf
A warehouse keeps crates in a circular rack, labelled with distinct numbers in increasing order. During a night shift the rack was spun, so the labels now start somewhere in the middle of the original order: for example, [10, 20, 30, 40, 50] may now read [30, 40, 50, 10, 20]. Nobody remembers by how many places it was turned.
Given the array nums that results and an integer target, return the index of target in nums, or -1 if it is missing. All labels are distinct. The array can be very long, so your solution must run in O(log n) time.
Example 1
- Input:
- nums = [30,40,50,10,20], target = 10
- Output:
- 3
- Explanation:
The label 10 sits at index 3 after the rotation.
Example 2
- Input:
- nums = [30,40,50,10,20], target = 35
- Output:
- -1
- Explanation:
35 is not on the rack, so the answer is -1.
Constraints
1 ≤ nums.length ≤ 106
-109 ≤ nums[i], target ≤ 109
All values of nums are distinct. nums is a sorted array rotated by an unknown number of positions (possibly zero).
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O(log n)
- Space
- O(1)