2.3.1 - Algorithm design and suitability

Specify the result before choosing the steps

A monitor receives an array of integer readings and an integer limit. It must return the zero-based index of the first reading strictly greater than the limit, or -1 if none qualifies. Readings may be negative, repeated or unsorted. An empty array is permitted. The algorithm must leave the input unchanged.

For readings [6, 12, 12, 4] and limit 10, the result is 1. Returning 12 confuses the value with its index. Returning 2 ignores the word first. With limit 12 the result is -1 because equality does not qualify. With no readings the result is also -1. These decisions are part of the problem, not details to guess while programming.

Separate necessary information from an unnecessary implementation restriction. The requirement does not demand sorting. Sorting would change positions and could destroy the meaning of first in the original sequence. A proposed optimisation must preserve the contract, including output identity and side effects.

Maintain a meaning for each changing variable

Design the scan around the meaning of its current index. Start i at 0. While i is a valid index, compare that reading with the limit. Return i immediately if it qualifies; otherwise increase i by one. If the loop finishes, return -1.

Initially that prefix is empty, so the claim is true. After a failure, increasing i extends the checked prefix by one. If a reading qualifies, the invariant proves it is the first. When i reaches the length, every reading has failed, so -1 is correct.

The index increases on each unsuccessful iteration and is bounded by the finite array length. This proves termination. Checking that i is in range before accessing the array also prevents an out-of-bounds read on an empty array or after the last failure.

Trace [2, 7, 5, 11] with limit 8:

The early return means no later reading is examined. A trace records the operations the algorithm actually performs, not every possible array row. It is different from a test: tracing follows state; testing compares the observed result with an independently chosen expected result.

Keep one algorithm consistent across representations

A flowchart, pseudocode and program code can describe the same decisions and updates. Changing the notation must not change their meaning.

In a flowchart, a terminal oval marks start/end, a process rectangle changes state, a decision diamond chooses a labelled branch, and an input/output parallelogram communicates a result. Arrowheads show the execution direction. A loop arrow returns to the condition, not to initialization, which would keep resetting i to zero.

[DIAGRAM: Flowchart for first reading strictly above a limit with range check before array access and failure loop; asset_slug: first-above-flowchart; caption: The scan checks the index before reading and loops back only after increasing it.]

The complete flow is also available in text: Start → i = 0 → decide i < n. No → return -1 → End. Yes → decide readings[i] > limit. Yes → return i → End. No → i = i + 1 → return to i < n. Here n is the number of readings.

OCR-style pseudocode uses = for assignment and == for equality. The following conditions use < and >; the array is zero-indexed and .length gives its length.

function firstAbove(readings, limit)
    i = 0
    while i < readings.length
        if readings[i] > limit then
            return i
        endif
        i = i + 1
    endwhile
    return -1
endfunction

Python 3 uses indentation rather than endif/endwhile, and len rather than .length:

def first_above(readings, limit):
    i = 0
    while i < len(readings):
        if readings[i] > limit:
            return i
        i = i + 1
    return -1