253. Search a Rotated Array
Challenge1000 ms256 MBSolved by 0%
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.
Input7 0
4 5 6 7 0 1 2
Output4
Notefinds a value in the rotated-round part
Input7 3
4 5 6 7 0 1 2
Output-1
Notelooks for a value that is not present at all
Hint 1Approach
Hint 2Approach
Hint 3Pseudocode
Hint 4Full solution