Wrapped flight recorder

The tape holds frames in increasing order except in one place, where the recorder wrapped to the start. One broken step is still enough to binary search.

The problem

A flight recorder writes one frame per second onto a fixed-length loop of tape. Frames carry a strictly increasing counter, and at the end of the loop the head wraps to the start and overwrites the oldest. Reading from position 0 therefore gives a strictly increasing list that has been rotated: the counters climb, drop once at the wrap, then climb again.

Investigators know the counter they want. Give them its position, or tell them it was overwritten. You do not know where the wrap is, and finding it first is not required. Counters are distinct — the recorder never reuses one in a flight.

Input. tape — a list of distinct integers, a rotation of a strictly increasing list. frame — the counter being looked for.

Output. The index of frame in tape, or -1 if it is not on the tape.

Example.

tape = [58, 61, 70, 4, 9, 21, 33], frame = 9    ->  4
tape = [58, 61, 70, 4, 9, 21, 33], frame = 55   ->  -1

The wrap sits between 70 and 4, and counter 9 is at index 4. Counter 55 falls in the gap between 33 and 58 and was never written.

A second example, where the tape did not wrap at all:

tape = [12, 15, 19], frame = 12   ->  0

A rotation by zero is still a rotation; the method must not assume a drop exists.

Constraints.

• 1 <= len(tape) <= 10^5
• 0 <= tape[i] <= 10^9, all values distinct
• tape is some rotation of a strictly increasing list
• 0 <= frame <= 10^9

Hints

Approach

Brute force

Compare every counter from index 0: up to 10⁵ per query, and it throws away the fact that the tape is nearly sorted.

The insight

A rotation has exactly one drop, so of the two halves either side of the midpoint at least one is a plain sorted run — and a sorted run can be ruled in or out with two comparisons.

The wrap sits at one index, so splitting at mid puts it in at most one half; the other half is ordinary increasing data whose extremes are its endpoints. Test whether frame lies between them: if it does, continue there; if not, it can only be in the half holding the wrap. Either way the window halves — the precondition that matters is not sortedness but a rule that discards half the space per step.

Algorithm

1. Set lo = 0, hi = len(tape) - 1.
2. While lo <= hi, take mid = (lo + hi) // 2 and return mid on a match.
3. If tape[lo] <= tape[mid] the left half is sorted: go left when tape[lo] <= frame < tape[mid], otherwise right.
4. Otherwise the right half is sorted: go right when tape[mid] < frame <= tape[hi], otherwise left.
5. Return -1 once the window empties.

Complexity

Time O(log n) — every iteration discards a half, wherever the wrap is. Space O(1); three indices.

Solution

"""Wrapped flight recorder — binary search on a rotated strictly increasing tape."""


def solve(tape, frame):
    lo, hi = 0, len(tape) - 1
    while lo <= hi:                       # invariant: if frame is on the tape, it is in [lo, hi]
        mid = (lo + hi) // 2
        if tape[mid] == frame:
            return mid
        if tape[lo] <= tape[mid]:
            # Left half holds no wrap, so its counters run tape[lo]..tape[mid].
            if tape[lo] <= frame < tape[mid]:
                hi = mid - 1
            else:
                lo = mid + 1
        else:
            # The wrap is on the left, so the right half is the clean run.
            if tape[mid] < frame <= tape[hi]:
                lo = mid + 1
            else:
                hi = mid - 1
    return -1

TESTS = [
    (([58, 61, 70, 4, 9, 21, 33], 9), 4),
    (([58, 61, 70, 4, 9, 21, 33], 55), -1),
    (([12, 15, 19], 12), 0),
    (([7], 7), 0),
    (([7], 3), -1),
    (([4, 9, 21, 33, 58, 61, 70], 70), 6),
    (([33, 58, 61, 70, 4, 9, 21], 33), 0),
    (([33, 58, 61, 70, 4, 9, 21], 21), 6),
    (([5, 1, 2, 3, 4], 1), 1),
]

Pitfalls

• Using < instead of <= in tape[lo] <= tape[mid]. Once the window is two entries lo == mid, and a strict test calls the left half unsorted; the search walks the wrong way and returns -1 for a frame that is on the tape.
• Getting the endpoint test half-open the wrong way. The sorted half includes tape[lo] and excludes tape[mid], already compared. tape[lo] < frame misses a frame sitting at tape[lo] — that is [12, 15, 19] with frame 12 returning -1.
• Assuming the drop exists. An unrotated tape is legal, so a step written as "find where the counter decreases" runs off the end and then indexes the tape with its length.

Variants

• Toll plaza minute — the same log with its order intact, where the trap is duplicates rather than a wrap.
• Staircase price board — partly ordered data again, where one comparison still discards a whole region.