Search in Rotated Sorted Array
Search for a target in a rotated sorted array (no duplicates) in O(log N).
Input format
The first line contains N and the target. The second line contains N distinct integers — a sorted array rotated at some pivot.
Output format
Print the 0-based index of the target, or -1 if absent.
Constraints
- Values fit in a 64-bit signed integer
- Trailing whitespace and a trailing newline are ignored by the judge
Read from stdin, write to stdout. Sample cases below show the exact format.
Sample cases
Example 1
Input
7 0
4 5 6 7 0 1 2Expected output
4Example 2
Input
7 3
4 5 6 7 0 1 2Expected output
-1