Linear search: contracts, traces and cost

By UK GCSE Computer Science · independent study · myAudience

Original built-in imagegen teaching raster; author inspected original and three served sizes2026-10-04. Independent derivative review pending. · Generated project artwork; no copied exam or publisher illustration. Independent rights/publication review pending.

Linear search: contracts, traces and cost

Searching asks whether a target exists and often where it appears. Define the return contract before writing a loop: this linear search returns the first matching index, or -1 when no match exists. Entry skills are list indexing and loop invariants. The input is a finite sequence whose values can be compared to the target. No sorting assumption is needed. Checking each position in order makes the first-match promise achievable even with duplicates. Returning False would be ambiguous if the caller expects index 0, because Python treats zero as false in conditions.

The algorithm starts at the first element, compares it to the target, returns its index on equality, and otherwise advances. If all positions are exhausted it returns the failure marker. The invariant is that every earlier position has been examined and is not the target. Therefore when a match is found, no earlier match exists. For [12,7,12,4] and target 12, the algorithm returns zero after one comparison. For target 4 it returns three after four comparisons. For target 9 it makes four comparisons and returns -1. The empty sequence makes none.

Efficiency needs a defined unit. Here we count equality comparisons, not seconds. Searching n elements has best case one comparison when n>0 and the target is first; worst case n when it is absent or last. If a present target is equally likely to occupy any position, the average count is (n+1)/2. That average is not valid for a workload dominated by absent targets or repeated first-item requests. Big-O notation is optional enrichment, not a required formal comparison: the worst comparison count grows linearly, often written O(n). This assumes equality comparison itself has fixed cost; long strings may violate that simplification.

The implementation exposes the comparison count so a test can inspect work as well as output. It does not use list.index because the lesson needs visible mechanics. A library method can be sensible in an application, but hiding the loop does not explain its correctness. No timing measurement here establishes real hardware performance. The generated search visual traces all four comparisons for target 4 in the unsorted list [12,7,12,4], then distinguishes the first-match target 12 and absent target 9 cases. Linear search cannot safely discard a half based on order when its input is unsorted.

A search returning one index is not a complete duplicate report. If the task becomes finding every matching record, remove the early success return and accumulate indices until all data is examined. That changed output contract changes both the proof and best-case work. An empty result list is unambiguous as an all-match failure. Testing only unique input misses this distinction, so the demanding transfer uses repeated values and asks you to state how a caller interprets the output.

Runnable original Python 3 example (also saved verbatim in examples for CLI execution):
```python
def linear_search(values, target):
"""Return (first index or -1, equality comparisons); finite sequence."""
comparisons = 0
for index in range(len(values)):
comparisons += 1
if values[index] == target:
return index, comparisons
return -1, comparisons

assert linear_search([12, 7, 12, 4], 12) == (0, 1)
assert linear_search([12, 7, 12, 4], 9) == (-1, 4)
assert linear_search([], 9) == (-1, 0)
```

Worked example: Trace target 4 in [12,7,12,4] and contrast target 12.

Compare 12,7,12,4 in order until equality; four comparisons.

Return index 3, since indexing starts at zero.

For target 12 the first element matches; return index 0 after one comparison.

Answer: (3,4) versus (0,1).

Check your understanding: Transfer: return every matching index in [8,3,8,8,2] for target 8. Explain the count of comparisons and an invariant; say why sorting first may damage the required answer.

Answer: Return [0,2,3] after five comparisons. After k items, the result contains exactly the matching indices less than k in ascending order. Sorting changes positions, so indices would no longer refer to the original input unless original indices are preserved.

Why: The answer must satisfy completeness and preservation of position, not just membership. Early return would miss later duplicates. A sorted value list can be useful for another contract but cannot silently replace the original ordering.