814. Is It In There At All

A list of n integers was sorted into non-decreasing order, duplicates allowed, and then rotated left by some number of positions. Then q questions are asked about it, each naming a value.

For each question print 1 if the value occurs somewhere in the list and 0 if it does not.

list 2 5 6 0 0 1 2, asking 0, 3, 2 -> 1, 0, 1 list 1 1 1 1 1, asking 1, 2 -> 1, 0

## What this adds to problem 253

Problem 253 searches a rotated list of DISTINCT values and prints the index where the value sits. It rests on one observation: cut anywhere, and at least one of the two halves is still properly sorted, which you can detect by comparing a[lo] with a[mid].

Duplicates break both halves of that sentence.

First, the detection fails. In 1 1 1 0 1 1 1 with lo = 0, mid = 3, hi = 6 you have a[lo] == a[mid] == a[hi] == 1, and in 1 1 1 1 0 1 1 you have exactly the same three readings. The rotation point is on opposite sides. No test that reads only those three entries can separate them, so the "which half is sorted" question has no answer here.

Second, the question changes. An index is no longer well defined, because a value can occur many times and the rotation itself is not determined, so this asks only whether the value is present. That is the most an algorithm can report without reading the whole list.

## The third branch

a[mid] == x found it, answer 1 a[lo] == a[mid] == a[hi] no information, so lo = lo + 1 and hi = hi - 1 a[lo] <= a[mid] the left half is sorted otherwise the right half is sorted

Shrinking both ends by one in the blind case is safe because a[lo] and a[hi] were both compared against x already, through a[mid]: they are equal to a[mid], and a[mid] != x was established on the line above. So neither discarded entry could have been the answer.

When one of the halves IS known to be sorted, the test must use BOTH of its ends. With the left half sorted, x is inside it only when a[lo] <= x < a[mid]. Checking only x < a[mid] discards the wrong half whenever x is smaller than everything in the sorted part.

## The invariant the loop maintains

> if x occurs anywhere in the list, it occurs somewhere in a[lo .. hi].

Every branch discards only entries that are provably not x, or that lie outside the sorted range that could contain x, so the invariant survives all of them.

## Why the loop terminates

Each branch moves lo up or hi down by at least one, so the number of live indices strictly falls. The loop is written while (lo <= hi) rather than while (lo < hi) because the answer here is a yes or no rather than a position, so a single remaining index still has to be examined.

## What is printed when nothing qualifies

When lo passes hi the range is empty, the invariant says x is nowhere in the list, and the answer is 0. That is the ordinary outcome of the loop, not a special case.

## Size of the numbers

Values reach 10^9 and are only ever compared against each other and against x, so a signed 32-bit integer is enough and nothing overflows. The indices reach 100000. What this problem can exhaust is TIME rather than range: q * n reaches 10^7 comparisons in the worst case, which is the budget the small q protects.

## Cost

O(log n) per question when the values are mostly distinct, but O(n) in the worst case, when the blind branch fires almost every iteration. That is why q is kept small in the constraints: the honest bound for the whole run is O(q * n), and pretending otherwise is the mistake this problem is here to prevent.

Space O(n).

Constraints - `1 ≤ n ≤ 100000` - `1 ≤ q ≤ 100` - `-1000000000 ≤ a[i] ≤ 1000000000` - Values may repeat.