Search in a rotated sorted array
Asked at Citadel
A sorted array of distinct integers was rotated at an unknown pivot, think of a circular buffer of timestamps whose write head wrapped around.
a = [4, 5, 6, 7, 0, 1, 2], target = 0
-> 4
a = [4, 5, 6, 7, 0, 1, 2], target = 3
-> -1
Return the index of target, or -1. Aim for .
Show a hint
Cut the array at mid. At least one of the two halves is a normal sorted array, which one, and how can you tell in ?
Your answer
This one is open-ended. Work it through, then check your reasoning against the full solution.