819. The Log With No Length Header

A sensor writes its readings to a log in non-decreasing order. The log carries no length header: the file simply ends. You are given a threshold x and must report the FIRST position in the log whose reading is at least x.

Binary search needs an upper bound and there is none. The fix is to manufacture one by DOUBLING, and this problem measures whether you did it, by asking for the probe count as well as the answer.

## The probe schedule, fixed exactly

Probe j, for j = 0, 1, 2 and so on, looks at index 2^j - 1. So the probed indices are

0, 1, 3, 7, 15, 31, 63, 127, and so on

Make the probes in that order. STOP at the first probe j for which either

2^j - 1 is not a valid index (the log is shorter than that) the reading there is >= x

That stopping probe counts. If the very first probe stops you, the count is 1.

Print two integers on one line: the index of the first reading at least x, and the number of probes made.

x = 5, log 1 3 5 7 9 -> 2 3 x = 100, log 1 3 5 7 9 -> 5 4 x = 1, log 1 -> 0 1 x = 7, log 1 2 3 4 5 6 7 8 9 10 -> 6 4

In the first line, probes at indices 0, 1 and 3 read 1, 3 and 7; the third one is at least 5, so three probes were made and the search then runs inside indices 2 to 3.

## Why doubling is the right bound

After probe j has failed, every index up to 2^j - 1 is known to hold a reading below x, so the answer is strictly greater. Doubling means probe j+1 skips over as much ground as everything examined so far put together, and the number of probes to reach a true answer at position k is about log2(k) + 1, not log2(length). That matters when the log is enormous and the answer is near the front: a log of a million readings whose answer is at index 3 costs three probes, not twenty.

Stepping forward by a constant instead, say a thousand at a time, costs O(k) probes and is the trap this schedule is written to expose.

## The second search, and its invariant

The stopping probe hands you a bracket. Let prev be one past the previously probed index, or 0 if the first probe stopped you, and let hi be the stopping index, or the log length if the probe ran off the end. Then

> the first index with a reading at least x lies in [prev, hi].

That is true because everything below prev was shown to be too small, and hi either holds a large enough reading or is one past the end, which is the sentinel answer. Now run the ordinary lower bound of problem 241 on [prev, hi].

## Why the loops terminate

The doubling loop stops because 2^j - 1 eventually exceeds any finite length. The lower bound stops because mid = lo + (hi - lo) / 2 satisfies lo <= mid < hi, so each branch strictly shrinks hi - lo.

## What is printed when nothing qualifies

When every reading is below x there is no qualifying index, and the answer is the LENGTH of the log, which is one past the last valid index. That is the same convention problem 241 uses, and it is deliberately not -1: the value doubles as the position where x would be inserted. The probe count in that case is the first j with 2^j - 1 past the end, plus one.

## Size of the numbers

The readings reach 10^9 in magnitude and are only compared against x, so nothing overflows a signed 32-bit integer. The probe index 2^j - 1 is the expression to watch: after about 31 doublings it passes the 32-bit ceiling, so compute it in a 64-bit type, or stop as soon as it exceeds the length, which this schedule does anyway.

## Cost

Time O(log k) where k is the answer, plus the unavoidable cost of reading the file. Space O(length).

Constraints - The log holds between `1` and `200000` readings. - `-1000000000 ≤ reading ≤ 1000000000` - `-1000000000 ≤ x ≤ 1000000000` - The readings are non-decreasing.