Binary SearchArray
A sorted array of distinct integers was rotated at an unknown pivot (for example 0 1 2 4 5 6 7 became 4 5 6 7 0 1 2). Find the index of a target value in O(log n).
Input
Line 1: n and the target. Line 2: the rotated array.
Output
Print the index of the target, or -1 if it is absent.
Constraints
1 <= n <= 10^5 All values are distinct.
Example 1
Input
7 0 4 5 6 7 0 1 2
Output
4
0 sits at index 4.
Example 2
Input
7 3 4 5 6 7 0 1 2
Output
-1
3 is not present.