A bus depot keeps its departure times (as distinct integers) in a sorted list, but the board started printing from the middle, so the list was rotated: for example 40 52 61 3 9 17 28.
Given the rotated list and a time key, print the index (0-based) where key appears, or -1 if it is not there. Aim for O(log n).
Constraints
- 1 ≤ n ≤ 100000
- values are distinct
Input and output
- Input
- Line 1: n. Line 2: n distinct integers (a rotated sorted list). Line 3: key.
- Output
- One integer: the index of key, or -1.
Examples
Input 1
7
40 52 61 3 9 17 28
9Output
49 sits at index 4 (counting from 0).
Input 2
5
8 10 1 4 6
7Output
-17 is not on the list.
Show hints
- After you pick a middle element, at least one half (left or right) is in sorted order.
- Check whether key lies inside the sorted half; if not, it must be in the other half.
Show the explanation
Binary search still works because one half of any window is always sorted. If a[lo] ≤ a[mid], the left half is sorted: search there when a[lo] ≤ key < a[mid], otherwise go right. Otherwise the right half is sorted: search there when a[mid] < key ≤ a[hi], otherwise go left. Each step halves the window, so it runs in O(log n).
Original UniCircle question. Last reviewed 22 Oct 2026.