Write search_rotated(nums: list[int], target: int) -> int.
nums was a strictly increasing list (all values distinct) that was then rotated: some prefix was cut off and moved to the end. For example [1, 3, 6, 8, 11, 14] rotated by 2 becomes [6, 8, 11, 14, 1, 3]. The rotation amount is unknown and may be 0. Return the index of target, or -1 if it isn't present.
Example: nums = [6, 8, 11, 14, 1, 3], target = 1 gives 4; target = 7 gives -1.
Constraints: 1 <= len(nums) <= 10^6, many queries against the same list.
Must be O(log n); a linear scan (including list.index / in) fails the performance test.
C++ / Java: you write searchRotatedAll(nums, targets), which returns search_rotated(nums, t) for every t in targets, in order, so the tests can run many searches on one big list. Write searchRotated as a helper and call it in a loop.
Show hint
split at mid. At least one of the two halves is still sorted normally, and for that half you can tell at a glance whether the target could be inside it.