816. Finding a Value on a Mountain
A list of n integers is a MOUNTAIN: there is an index p with 0 < p < n - 1 such that
a[0] < a[1] < ... < a[p] strictly rising
a[p] > a[p+1] > ... > a[n-1] strictly falling
Given a value x, print the SMALLEST index at which x occurs, or -1 if it does not occur.
Read at most a logarithmic number of entries: a linear scan is not the intended answer.
list 1 2 3 4 1, x = 3 -> 2
list 1 2 3 4 1, x = 9 -> -1
list 0 2 4 6 5 4 1, x = 4 -> 2 (it is also at index 5)
list 0 2 4 6 5 4 1, x = 1 -> 6
## Three searches, not one
The list is not sorted, so no single comparison against x can decide which half to keep. It
is, however, two sorted runs glued together, so:
1. find p, the peak
2. search a[0 .. p], which is strictly INCREASING
3. if that fails, search a[p .. n-1], which is strictly DECREASING
Doing the rising side first is what makes the answer the SMALLEST index without any extra work,
because every index on the rising side is at most p and every index on the falling side is at
least p. The peak itself belongs to step 2, and it holds the largest value, which occurs only
once, so nothing is double counted.
## Finding the peak
This is the loop from problem 252, and the argument is worth repeating because it is the one place where binary search runs on data that is not sorted at all.
Compare a[mid] with a[mid+1]. If a[mid] < a[mid+1] the list is rising at mid, and a
rising run must stop rising somewhere to the right, so the peak is at an index greater than
mid. Otherwise the list is already falling at mid, so mid itself may be the peak and
everything after it certainly is not.
Problem 252 accepts ANY peak because its input may have several. Here the mountain shape guarantees exactly one, so the index this loop returns is THE peak, and the two searches that follow depend on that.
## The two searches, and their invariants
On the rising side run a lower bound over [0, p]: keep the invariant that the first index with
a[i] >= x lies in [lo, hi], move lo = mid + 1 when a[mid] < x and hi = mid
otherwise. When lo == hi, check a[lo] == x before believing it. That check is the whole
difference between a lower bound and a search: the loop always returns a position, and only the
comparison decides whether the value is actually there.
On the falling side the comparison flips, because the run descends: move lo = mid + 1 when
a[mid] > x and hi = mid otherwise. The same final equality check applies.
## Why each loop terminates
All three loops use mid = lo + (hi - lo) / 2, which gives lo <= mid < hi while lo < hi,
and every branch either raises lo above mid or lowers hi to mid. So hi - lo falls by
at least one per iteration, and each loop finishes in at most log2(n) steps. Three loops,
about fifty-one entries read for n = 200000.
## What is printed when nothing qualifies
Both equality checks can fail, and then x is nowhere on the mountain, and the answer is -1.
It is not enough for one of them to fail: the rising search failing says only that x is not on
the rising side.
## Size of the numbers
Values reach 10^9 and are only compared, never combined, so a signed 32-bit integer holds
everything and nothing overflows. The indices reach 200000, so even a midpoint written
(lo + hi) / 2 would survive here. It is still written lo + (hi - lo) / 2 throughout,
because three loops is three chances to carry a bad habit into a problem where the range really
is 2 * 10^9.
## Cost
Time O(log n). Space O(n) for the list itself, O(1) for the search.
Constraints - `3 ≤ n ≤ 200000` - `-1000000000 ≤ a[i] ≤ 1000000000` - `-1000000000 ≤ x ≤ 1000000000` - The peak index `p` satisfies `0 < p < n - 1`.
Input
The first line contains two integers n and x.
The second line contains n integers forming a mountain: strictly increasing up to a single peak, then strictly decreasing.
Output
Print one integer, the smallest 0-based index whose value equals x, or -1 if no entry equals x. Print it alone on one line.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.