Finding the accession

A museum store is a grid of boxes, but the numbering runs through it in a single line. Two nested searches look natural here; one search is enough.

The problem

A museum store holds its accession numbers in identical boxes, each with the same number of slots. Boxes were filled in order: the first slot by slot, then the second, and so on. Numbers were issued in increasing order and never reused, so within a box the numbers ascend, and the first number in any box is larger than the last number in the box before it.

The registrar has a number off an old catalogue card and wants to know whether it is in the store at all. Pulling a box is slow, so touch as few slots as possible.

Input. boxes — a list of rows, each row the accession numbers in one box, left to right. code — the number being looked for.

Output. True if code is in the store, False otherwise.

Example.

boxes = [[1004, 1011, 1027, 1038],
         [1052, 1063, 1079, 1090],
         [1104, 1118, 1125, 1141]]
code  = 1079   ->  True

1079 sits in the second box, third slot.

A second example, where the number falls in the gap between two boxes:

code = 1100   ->  False
code = 1200   ->  False

1100 sits above the last number of box 2 and below the first of box 3, so it belongs nowhere. 1200 is past everything, the case that runs the search off the end.

Constraints.

• 0 <= len(boxes) <= 300, every row the same length
• 0 <= len(boxes[0]) <= 300
• 0 <= boxes[i][j] <= 10^9, strictly increasing when read box by box
• the store may be empty, and boxes may have no slots

Hints

Approach

Brute force

Walk every slot of every box until the number turns up or is passed: 90,000 reads for a full 300 by 300 store.

The insight

Reading the boxes end to end gives one ascending run, so a position p maps to boxes[p // cols][p % cols] and the whole store is a single sorted sequence.

Each box ascends and every box starts above the one before it, so joining them keeps the order. Over that virtual run the predicate "the number at position p is at least code" is false and then true — what binary search needs — and its first true is the only position that could hold code. One comparison there settles the question.

Algorithm

1. If there are no boxes, or the boxes have no slots, answer False.
2. Let rows and cols be the grid's shape; positions run to rows * cols.
3. Binary search for the first position whose number is at least code, reading position p as boxes[p // cols][p % cols].
4. If the search lands on rows * cols, every number is smaller: answer False.
5. Otherwise answer whether the number there equals code.

Complexity

Time O(log(rows · cols)) — 17 reads for a 90,000-slot store, against 90,000 for the walk. Space O(1).

Solution

"""Archive accession lookup — one binary search over the boxes read as a single run."""


def solve(boxes, code):
    if not boxes or not boxes[0]:
        return False
    rows, cols = len(boxes), len(boxes[0])

    # Boxes were filled slot by slot, box by box, and accession numbers only ever
    # increase, so position p -> boxes[p // cols][p % cols] is one ascending run.
    # P(p) = "the code at p is >= the query" is monotone; find the first True.
    lo, hi = 0, rows * cols
    while lo < hi:                     # invariant: the first True position is in [lo, hi]
        mid = (lo + hi) // 2
        if boxes[mid // cols][mid % cols] >= code:
            hi = mid
        else:
            lo = mid + 1
    # lo == rows * cols means every code in the store is smaller than the query.
    return lo < rows * cols and boxes[lo // cols][lo % cols] == code


SHELF = [[1004, 1011, 1027, 1038], [1052, 1063, 1079, 1090], [1104, 1118, 1125, 1141]]

TESTS = [
    ((SHELF, 1079), True),
    ((SHELF, 1100), False),            # falls in the gap between two boxes
    ((SHELF, 1004), True),             # the very first slot
    ((SHELF, 1141), True),             # the very last slot
    ((SHELF, 1200), False),            # past the end: the search runs off the run
    (([[7]], 3), False),
    (([[7]], 7), True),
    (([], 42), False),
    (([[]], 42), False),
]

Pitfalls

• Dropping the range check on the final position. With code = 1200 the search stops at position 12, one past the last slot, and indexing there raises IndexError. Test lo < rows * cols before reading.
• Dividing by the number of rows instead of the number of columns. On a non-square store p // rows picks the wrong box and quietly returns wrong answers; the row index divides by the row length.
• Assuming there is a boxes[0]. An empty store, or one of empty boxes, makes cols zero and every position a division by zero.

Variants

• First bag on the belt — the same first-true search, on a run that has been rotated.
• Dialling in the data cap — the same lower bound, over a computed quantity rather than stored numbers.