1602. Find It In a Rotated Sorted Array
An array of n DISTINCT integers was sorted increasingly and then rotated left
by some unknown amount. For each of q targets, print its 1-based position, or
-1 if it is absent.
``` 4 5 6 7 0 1 2 this is 0 1 2 4 5 6 7 rotated by 4
0 -> 5 3 -> -1 4 -> 1 ```
A rotation by 0 is allowed, so the array may be plainly sorted.
## What most people try first
A linear scan. Correct, O(n) per query, so 10^5 queries over 10^5 values is
10^10 comparisons.
The next idea is to find the rotation point first with one binary search, then binary search the correct half. That works and needs two searches. The version below needs one, and understanding why is the point of the problem.
## At every midpoint, one half is plainly sorted
Compare a[lo] with a[mid]:
if a[lo] <= a[mid]: the LEFT half is sorted, with no rotation point inside it
else: the RIGHT half is sorted
One of the two always holds, because the rotation point is a single place, so it can lie in at most one half. That is the whole insight.
Having identified the sorted half, you can decide in one comparison whether the target lies inside it, because a sorted range is bounded by its two ends:
if the left half is sorted:
if a[lo] <= x < a[mid]: search left
else: search right
else:
if a[mid] < x <= a[hi]: search right
else: search left
## Why the comparisons must be the way they are
The bounds are inclusive on the end that holds a real element and exclusive at
a[mid], which has already been tested for equality before this point. Writing
a[lo] <= x <= a[mid] instead would re-enter a range whose midpoint is known not
to match, which costs a step but is still correct. Writing a[lo] < x is the
real bug: it loses the target when it sits exactly at a[lo].
## Why distinctness matters
With duplicates the test a[lo] <= a[mid] stops deciding anything. On
2 2 2 0 2 the left half looks sorted and is not, and no comparison of two
elements can tell, so the worst case degrades to O(n). The constraints
guarantee distinct values for exactly that reason, and it is worth knowing that
the guarantee is what buys the logarithm.
## The boundary
n = 1 is both the whole array and a single element, and a rotation by 0 means
the array is sorted, so the method must not assume a rotation point exists.
Both are declared tests.
## Overflow
Values reach 10^9 in magnitude and nothing here adds two of them together:
every operation is a comparison. A signed 32 bit integer holds up to
2147483647, so 32 bits is sufficient throughout. Worth checking rather than
widening by reflex, since the neighbouring problems in this block do accumulate.
## Cost
O(log n) per query, so about 17 steps at n = 10^5, and O(q log n) overall.
Constraints - `1 ≤ n ≤ 100000` - `1 ≤ q ≤ 100000` - `-10^9 ≤ each value ≤ 10^9` - all `n` values are distinct - the array is a sorted array rotated left by an unknown amount, possibly by 0
Input
The first line contains the integer n.
The second line contains n distinct integers: a sorted array rotated left by an unknown amount.
The third line contains the integer q.
Each of the next q lines contains one integer, a target.
Output
Print one integer on its own line for each target, in the order given: its 1-based position in the array, or -1 if the array does not contain it.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.