253. Search a Rotated Array
A sorted array of distinct values has been rotated: some prefix was moved to
the end. For example 1 2 3 4 5 6 7 rotated becomes 4 5 6 7 1 2 3.
Print the index of x, or -1 if it is absent.
The array is no longer sorted, so a plain binary search fails. The key observation is that after cutting at any midpoint, at least ONE of the two halves is still properly sorted, and you can tell which by comparing its ends.
Once you know which half is sorted, you can check in one comparison whether
x lies inside its range. If it does, search there; if not, search the other
half.
Constraints - `1 ≤ n ≤ 200000` - `-1000000000 ≤ a[i] ≤ 1000000000` - All values are distinct.
Input
The first line contains two integers n and x.
The second line contains n distinct integers forming a rotated sorted array.
Output
Print the 0-based index of x, or -1 if it is not present.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.