First bag on the belt

Bags go onto the carousel in tag order, once round the loop, wrapping past slot zero. Read in slot order the tags climb, drop once, and climb again.

The problem

A baggage carousel is a loop of numbered slots. A flight is unloaded onto it in strictly increasing tag order, starting from whichever slot was at the chute, and the loading runs once around the loop — so it may wrap past slot 0 and continue from there.

The handler scans the belt in slot order and gets belt: two ascending runs, where every tag in the second is smaller than every tag in the first. If the loading never wrapped, belt is one ascending run. All tags are distinct. The transfer desk works from the first bag loaded, so it needs the smallest tag on the belt.

Input. belt — a list of distinct integers, the tags read out in slot order.

Output. The smallest tag on the belt.

Example.

belt = [58, 61, 64, 12, 19, 33, 47]   ->  12

Loading wrapped after slot 2. The second run starts at slot 3 with tag 12, which went on the belt first.

A second example, covering both ends of the behaviour:

belt = [3, 9, 14, 22]     ->  3
belt = [22, 33, 44, 5]    ->  5

The first never wrapped, so the answer sits at slot 0; the second wrapped on the last bag, so it sits at the far end. Code that assumes the drop is in the interior fails one of these.

Constraints.

• 1 <= len(belt) <= 10^5
• 0 <= belt[i] <= 10^9, all distinct
• belt is an ascending run rotated left by some amount, possibly zero

Hints

Approach

Brute force

Walk the belt until a tag is smaller than its predecessor, or fall off the end and answer belt[0]: up to 100,000 comparisons, when 17 will do.

The insight

Test each slot against the last slot, not against its neighbour: belt[i] <= belt[-1] is exactly "slot i is in the second run", false across the whole first run and true across the whole second.

Every tag in the first run is larger than every tag in the second, and belt[-1] is the largest tag of the second run, so the predicate flips once and never flips back. A belt that never wrapped makes it true everywhere, which lands on index 0 — the right answer there. That is the monotonicity binary search needs, and the belt itself is not sorted.

Algorithm

1. Record last = belt[-1], set lo = 0 and hi = len(belt) - 1.
2. While lo < hi, take mid = (lo + hi) // 2.
3. If belt[mid] <= last, mid is in the second run: set hi = mid.
4. Otherwise mid is still in the first run: set lo = mid + 1.
5. When the range collapses, return belt[lo].

Complexity

Time O(log n) — one comparison per halving, 17 for a full belt. Space O(1); the two indices and last.

Solution

"""First bag on the belt — binary search for the wrap point of a rotated run."""


def solve(belt):
    # Bags went onto the loop in strictly increasing tag order and the loading
    # wrapped past slot 0 at most once, so reading the slots in order gives two
    # ascending runs, every tag in the second smaller than every tag in the first.
    #
    # P(i) = "belt[i] <= belt[-1]" is exactly "slot i is in the second run".
    # That reads False ... False True ... True; the first True is the first bag.
    last = belt[-1]
    lo, hi = 0, len(belt) - 1
    while lo < hi:                      # invariant: the wrap point lies in [lo, hi]
        mid = (lo + hi) // 2
        if belt[mid] <= last:
            hi = mid                    # mid is in the second run, or is the last slot
        else:
            lo = mid + 1                # mid is still in the first, higher-tagged run
    return belt[lo]

TESTS = [
    (([58, 61, 64, 12, 19, 33, 47],), 12),
    (([3, 9, 14, 22],), 3),             # loading never wrapped: slot 0 holds it
    (([90, 11, 25, 40],), 11),          # wrapped after a single bag
    (([22, 33, 44, 5],), 5),            # wrap point in the very last slot
    (([7],), 7),                        # a one-slot belt
    (([40, 50, 60, 70, 10, 20, 30],), 10),
]

Pitfalls

• Comparing belt[mid] with belt[mid - 1] gives a predicate that is true at exactly one index, which is not monotone. Binary search on it walks into the wrong half and answers 61 on the first example.
• Using < instead of <= against last makes the final slot test false, so a belt that never wrapped reports the last tag rather than the first: 22 instead of 3.
• Returning lo hands back a slot number, not a tag: 3, not 12.

Variants

• High water — the same first-true shape, with the predicate built from a neighbouring reading instead.
• Finding the accession — a run with no wrap at all, where the predicate is a plain comparison with a query.