High water

A harbour gauge writes one water level every ten minutes. The log is not sorted, so nothing about it looks searchable — until you look at the question you are asking of each reading.

The problem

A harbour tide gauge records the water level every ten minutes into levels. Each tide has the same shape: the level rises strictly from the first reading to a single high water, then falls strictly to the last. No two neighbouring readings are equal, and high water is never the first or the last reading.

The lock keeper schedules the gate against that turn, so what is wanted is the index of high water — which reading it was, not how deep it got. Readings come off the gauge one at a time over a slow radio link, so the cost of an answer is the number of readings you pull.

Input. levels — a list of integers, water level in centimetres at reading 0, 1, 2, and so on.

Output. The index of the highest reading.

Example.

levels = [212, 268, 341, 390, 402, 355, 297, 218]   ->  4

The tide floods 212, 268, 341, 390, 402, then ebbs to 355, 297 and 218. Reading 4 is the turn, so the answer is 4 and not 402.

A second example, where the turn sits nowhere near the middle:

levels = [96, 410, 118]              ->  1
levels = [150, 240, 330, 415, 380]   ->  3

A one-step walk uphill from the middle degrades to a full scan on these.

Constraints.

• 3 <= len(levels) <= 10^5
• 1 <= levels[i] <= 10^9
• exactly one reading, strictly inside the log, is higher than every other

Hints

Approach

Brute force

Pull every reading and stop at the first one higher than its successor. For a 100,000-reading log that is 100,000 pulls over the radio link — correct, and about 6,000 times more traffic than needed.

The insight

"Reading i is already ebbing", meaning levels[i] > levels[i + 1], is false for every reading before the turn and true for every reading from the turn onward — so high water is the first true.

The tide floods strictly and then ebbs strictly, so the comparison never flips back: once past the turn you stay past it. Monotonicity of the predicate is the only precondition binary search needs — the data itself never has to be sorted, and here it is not.

Algorithm

1. Set lo = 0, hi = len(levels) - 1.
2. While lo < hi, take mid = (lo + hi) // 2.
3. Pull levels[mid] and levels[mid + 1].
4. If levels[mid] < levels[mid + 1] the tide is still flooding: set lo = mid + 1.
5. Otherwise mid is at or past the turn: set hi = mid.
6. When the range collapses, lo is high water.

Complexity

Time O(log n) — 17 halvings for a 100,000-reading log, two pulls each. Space O(1); two indices and nothing else.

Solution

"""High water — binary search on the predicate "the tide has already turned"."""


def solve(levels):
    # P(i) = "levels[i] > levels[i + 1]", i.e. reading i is already on the ebb.
    # A tide rises strictly to one high water and falls strictly afterwards, so P
    # reads False, False, ..., True, True and the first True is high water itself.
    lo, hi = 0, len(levels) - 1
    while lo < hi:                      # invariant: high water lies in [lo, hi]
        mid = (lo + hi) // 2
        if levels[mid] < levels[mid + 1]:
            lo = mid + 1                # still flooding, so high water is above mid
        else:
            hi = mid                    # mid is at or past the turn
    return lo

TESTS = [
    (([212, 268, 341, 390, 402, 355, 297, 218],), 4),
    (([96, 410, 118],), 1),             # turns on the second reading
    (([150, 240, 330, 415, 380],), 3),  # turns one reading from the end
    (([310, 420, 405],), 1),            # shortest legal log
    (([88, 96, 140, 133, 121, 104, 90],), 2),
    (([5, 9, 12, 30, 44, 60, 59],), 5),
]

Pitfalls

• Starting hi at len(levels) lets levels[mid + 1] read one past the end and the run dies with an IndexError. The predicate peeks forward, so the last probeable index is n - 2 — which hi = n - 1 gives you for free.
• Setting hi = mid - 1 when mid is already ebbing throws the answer away, because the ebbing reading you just found may be the turn itself. Only the flooding branch may discard mid.
• Returning levels[lo] answers a different question: 402 on the first example, when the schedule needs 4.

Variants

• Reading the balloon back — the same turn-finding search as step one, then a hunt for a given value on whichever side of the turn it lives.
• First bag on the belt — the same first-true search, with the predicate built against a fixed reading instead of a neighbour.