Find in Rotated Roster

medium

The same circular buffer, harder ask: the on-call roster ids was strictly increasing, then rotated at an unknown pivot — e.g. [4, 5, 6, 7, 0, 1, 2].

Given ids and a target badge, return the index of badge, or -1 if absent. Must be O(log n).

Example 1

in ids = [4, 5, 6, 7, 0, 1, 2], badge = 0

out 4

Example 2

in ids = [4, 5, 6, 7, 0, 1, 2], badge = 3

out -1

Example 3

in ids = [1], badge = 0

out -1

Constraints

· 1 <= len(ids) <= 2000
· -10^4 <= ids[i], badge <= 10^4
· all values distinct
· ids is a rotation of a sorted list