Reading the balloon back

A balloon climbs to one ceiling and comes down. The altitude log is not sorted, but it is two sorted runs glued at a point you have to find first.

The problem

A hot-air balloon logs its altitude once a minute. Every flight has the same shape: the altitude rises strictly from take-off to a single ceiling minute, then falls strictly to landing. Neighbouring readings are never equal.

The examiner asks when the balloon first passed a stated altitude. Each reading costs a radio round trip to the recorder, so a solution gets about sixty reads for a thousand-minute flight — a scan of the whole log is not affordable.

Input. altitudes — a list of integers, metres above ground at minute 0, 1, 2, and so on. target — the altitude asked about.

Output. The smallest index at which the altitude equals target, or -1 if the balloon was never at exactly that height.

Example.

altitudes = [90, 410, 980, 1730, 2600, 2140, 1310, 640, 120], target = 1310  ->  6
altitudes = [90, 410, 980, 1730, 2600, 2140, 1310, 640, 120], target = 1000  ->  -1

1310 metres appears once, on the way down, at minute 6. The balloon passed through 1000 metres twice but never logged it, so the answer is -1.

A second example, where the altitude occurs twice:

altitudes = [90, 410, 980, 1730, 2600, 2140, 980, 640, 120], target = 980  ->  2

980 shows up at minute 2 on the climb and again at minute 6 on the descent. The question asks when it was first reached, so the climb wins.

Constraints.

• 3 <= len(altitudes) <= 10^4
• 0 <= altitudes[i] <= 10^9, 0 <= target <= 10^9
• exactly one minute, strictly inside the log, is higher than every other

Hints

Approach

Brute force

Read every minute and return the first match: 1,000 round trips for a 1,000-minute flight, against a budget of sixty.

The insight

A climb-then-descend log is two monotone runs, so one search finds the ceiling and two more search the runs — each on a predicate that is false then true.

The ceiling comes from the same trick used to find any peak: altitudes[i] > altitudes[i + 1] is false while climbing and true from the ceiling on, so its first true is the ceiling. Splitting there gives an ascending run where "at least target" is monotone, and a descending run where "at most target" is. Nothing else about the log has to be sorted.

Algorithm

1. Binary search for the ceiling: first index where the reading is not below its successor.
2. Binary search the climb, from 0 to the ceiling, for the leftmost altitude at least target.
3. If that index is in range and matches exactly, return it — it is the earliest.
4. Binary search the descent, past the ceiling to the end, for the leftmost altitude at most target.
5. If that index is in range and matches exactly, return it.
6. Otherwise return -1.

Complexity

Time O(log n) — three binary searches, 14 reads each for a 10,000-minute flight. Space O(1); a handful of indices.

Solution

"""Balloon altitude probe — find the turn, then one binary search on each side."""


def turn_index(altitudes):
    """First minute that is not lower than the next: the top of the flight."""
    lo, hi = 0, len(altitudes) - 1
    while lo < hi:                            # invariant: the top lies in [lo, hi]
        mid = (lo + hi) // 2
        if altitudes[mid] < altitudes[mid + 1]:
            lo = mid + 1
        else:
            hi = mid
    return lo


def first_at_least(altitudes, lo, hi, target):
    """Leftmost minute in the climb whose altitude is >= target, else hi + 1."""
    while lo <= hi:
        mid = (lo + hi) // 2
        if altitudes[mid] >= target:
            hi = mid - 1
        else:
            lo = mid + 1
    return lo


def first_at_most(altitudes, lo, hi, target):
    """Leftmost minute in the descent whose altitude is <= target, else hi + 1."""
    while lo <= hi:
        mid = (lo + hi) // 2
        if altitudes[mid] <= target:
            hi = mid - 1
        else:
            lo = mid + 1
    return lo


def solve(altitudes, target):
    top = turn_index(altitudes)

    # The climb is ascending, so "altitude >= target" is monotone across it.
    i = first_at_least(altitudes, 0, top, target)
    if i <= top and altitudes[i] == target:
        return i                              # the climb comes first, so it wins

    # The descent is descending: the same predicate is monotone the other way.
    j = first_at_most(altitudes, top + 1, len(altitudes) - 1, target)
    if j < len(altitudes) and altitudes[j] == target:
        return j
    return -1

TESTS = [
    (([90, 410, 980, 1730, 2600, 2140, 1310, 640, 120], 1310), 6),
    (([90, 410, 980, 1730, 2600, 2140, 1310, 640, 120], 980), 2),
    (([90, 410, 980, 1730, 2600, 2140, 1310, 640, 120], 2600), 4),
    (([90, 410, 980, 1730, 2600, 2140, 1310, 640, 120], 1000), -1),
    (([90, 410, 980, 1730, 2600, 2140, 980, 640, 120], 980), 2),  # on both sides
    (([5, 12, 4], 4), 2),
    (([5, 12, 4], 5), 0),
    (([5, 12, 4], 12), 1),
]

Pitfalls

• Searching the descent first, or searching both and returning either match gives 6 on the second example instead of 2. The climb has to be resolved first.
• Reusing the ascending comparison on the descent searches a run that is ordered the other way, and lands somewhere arbitrary: the test has to flip to altitudes[mid] <= target.
• Forgetting the "not found" position. Both side searches can return one past their range, so an unguarded altitudes[i] raises IndexError, and an unguarded equality check reports a neighbour as a hit.

Variants

• High water — just step one of this problem: find the turn and stop.
• First bag on the belt — another two-run sequence, where one comparison against a fixed element does the whole job.