The problem
The stop numbers of a circular route were stored from smallest to largest, with no repeats. Then the list was rotated: some values from the start were moved to the end. For example, [3, 5, 9, 12, 15, 18, 22] might become [15, 18, 22, 3, 5, 9, 12]. You are not told where the rotation happened. Return the index of target, or -1 if it is not in the list.
search_rotated([15, 18, 22, 3, 5, 9, 12], 5) # 4
search_rotated([15, 18, 22, 3, 5, 9, 12], 13) # -1
search_rotated([1, 2, 3, 4, 5], 4) # 3 (not rotated)
In the large tests, the list counts every value you read from it. A binary search stays well under the limit. Anything that goes through the whole list goes over it. This includes in, .index(), list(…), sorted(…) and slicing.
Limits
- Up to 1,000,000 values, all different. At most 80 reads on the large tests.
- The list may not be rotated at all, and it may be empty.
Builds on BSRC-2 The invariant and BSRC-6 Off-by-one traps.
Continue on a laptop
Practice runs Python in the browser and needs a keyboard and a wider screen. Read the problem and open hints here, then write your solution on a laptop. Progress is saved per browser for now, so hints opened here stay on this device.
Need a hint?0 of 3 opened
- Hint 1Nudge
- Hint 2Approach Open hint 1 first
- Hint 3Pseudocode Open hint 2 first
- Worked solutionlast resort Opens after all 3 hints
Ctrl + Enter runs the tests. Tab indents; press Esc, then Tab, to leave the editor.
| # | Test | Result | Reads · time |
|---|---|---|---|
| 1 | In the right-hand part | Not run | |
| 2 | In the left-hand part | Not run | |
| 3 | Not in the list | Not run | |
| 4 | Not rotated at all | Not run | |
| 5 | Rotated by one, target first | Not run | |
| 6 | Rotated so the smallest is last | Not run | |
| 7 | One value | Not run | |
| 8 | Empty list | Not run | |
| 9 | Two values | Not run | |
| 10 | A million values, at most 80 reads | Not run | |
| 11 | A million values, target not in the list | Not run |