820. Where the Value Meets Its Index

A list holds n integers in STRICTLY increasing order. Print the smallest 0-based index i with a[i] == i, or -1 if no index satisfies that.

-10 -5 0 3 7 -> 3 1 2 3 4 5 -> -1 0 1 2 -> 0 -6 -4 -2 0 2 5 6 -> 5

## Why a binary search applies at all

a[i] == i is not a comparison against a fixed value, so the list being sorted does not obviously help. Shift the question instead. Define

d[i] = a[i] - i

and ask for the smallest i with d[i] == 0.

d is NON-DECREASING, and that is what makes the search legal. The values are integers and strictly increasing, so a[i+1] >= a[i] + 1, and therefore

d[i+1] = a[i+1] - (i+1) >= a[i] + 1 - i - 1 = a[i] - i = d[i]

Both halves of that argument are needed. Integers alone are not enough, because a list that merely does not decrease can have d fall: a = 5 5 gives d = 5 4. Strictly increasing alone is not enough either, because a list of non-integers can step up by less than one.

Note that d is non-decreasing rather than strictly increasing, so the value 0 may occur many times, which is exactly why the question asks for the SMALLEST such index rather than any.

## The invariant the loop maintains

Run the lower bound over d with lo = 0 and hi = n, keeping:

> the first index with d[i] >= 0 lies in [lo, hi].

If d[mid] < 0 then every index up to mid also has a negative d, since d never decreases going backwards, so lo = mid + 1. Otherwise mid may itself be the first non-negative one, so hi = mid.

hi starts at n and not n - 1, because "every d is negative" is a real possibility and the loop has to be able to land one past the end to express it.

## Why the loop terminates

mid = lo + (hi - lo) / 2 satisfies lo <= mid < hi while lo < hi, so one branch raises lo above mid and the other lowers hi to mid. The gap closes by at least one each iteration, in at most log2(n) steps.

## What is printed when nothing qualifies

The lower bound finds the first index with d[i] >= 0, which is not the same thing as d[i] == 0. Two separate failures are possible and both mean -1:

lo == n every d is negative, so a[i] < i everywhere d[lo] > 0 d jumped from negative straight past zero

The second is the one people forget. On 1 2 3 4 5 the values of d are 1 1 1 1 1, the lower bound returns 0, and a[0] is 1, not 0. Test lo < n FIRST, then test a[lo] == lo; reversing the order reads past the end of the list.

## Size of the numbers

a[i] - i is the only arithmetic in the whole solution. With a[i] as low as -10^9 and i as high as 200000, the difference reaches about -1000200000, which still fits in a signed 32-bit integer, so nothing overflows. It fits by less than a factor of two, though, and that is exactly the margin that disappears when constraints are widened later, so a 64-bit type for the difference is the safer habit.

## Cost

Time O(log n). Space O(n) for the list, O(1) for the search.

Constraints - `1 ≤ n ≤ 200000` - `-1000000000 ≤ a[i] ≤ 1000000000` - The values are strictly increasing, so they are all distinct.