aiMOOC

Searching and sorting algorithms - Computing Year 8

QR-Code

Introduction

Choose and compare linear search, binary search and bubble sort using exact original traces and tested Python functions. Distinguish sorted-data requirements, matching-index contracts and operation counts from total runtime. Year 8 placement is editorial within England’s KS3 Computing pathway.

Define the search question and sorted-data precondition

A search method needs a clear question and valid input assumptions. We seek an integer target in a list. Linear search examines values from the beginning until it finds a match or reaches the end. It works whether or not the list is sorted. Our version returns the first matching index and the number of item probes performed by its search loop. None means no match; index zero is a successful result, not a failure to be tested by simple truthiness.

For the original unsorted list four, two, seven, nine, finding seven visits four, then two, then seven. It returns index two after three probes. Finding the first four requires one probe; searching for absent twelve requires four. For an empty list, no items can be inspected, so the result is None and zero probes. Repeated values are legitimate: the first-match rule determines which index is returned.

def check_values(values):
    if type(values) is not list or len(values) > 32:
        raise ValueError("Use a list of at most thirty-two integers")
    for value in values:
        if type(value) is not int or not (value >= -1000 and 1000 >= value):
            raise ValueError("List values must be whole integers from -1000 to 1000")

def linear_search(values, target):
    check_values(values)
    if type(target) is not int:
        raise ValueError("Use an integer target")
    probes = 0
    for index, value in enumerate(values):
        probes += 1
        if value == target:
            return index, probes
    return None, probes

The helper validates a deliberately small learning interface: at most thirty-two exact integer list values from minus one thousand through one thousand. The target may be any integer; Boolean targets and nonintegers are rejected. Those limits are not mathematical limits of search algorithms. Validation has its own work. The reported probes count inspected search items only; they do not include every validation step, loop condition or Python operation.

Binary search uses a stronger precondition: values must be in ascending order under the same comparison rule. It checks a middle item, then discards the half that cannot contain the target. That discard is justified by sorted order. Without it, a smaller or larger value elsewhere may be discarded incorrectly. The original unsorted four-two-seven-nine list is therefore not valid input for binary search, even if one target might happen to be found.

Sorting creates a different index arrangement. If we sort that example to two-four-seven-nine, target seven has index two in the sorted copy; another target such as four changes from index zero in the original to index one in the sorted copy. Do not return a sorted-copy index while claiming it identifies the original row unless you preserve and map original identities deliberately.

Use cards and zero-based position labels for a paper trace. Mark the search range and each inspected value. Practical programming evidence requires running the actual functions and recording expected versus actual results. A photographed program or an imagined trace is not evidence of a learner's own execution.

Trace a precise binary-search range

Keep both ends of the current search range precise. Our binary search uses inclusive low and high indexes and chooses the lower middle when two middle positions are possible. The middle index is the integer quotient of low plus high divided by two. If the target is greater than that item, move low to middle plus one. Otherwise, after equality has failed, move high to middle minus one. Both updates exclude the already inspected middle, so the range must shrink.

def binary_search(values, target):
    check_values(values)
    if type(target) is not int:
        raise ValueError("Use an integer target")
    for index in range(1, len(values)):
        if values[index - 1] > values[index]:
            raise ValueError("Binary search requires ascending sorted values")
    low = 0
    high = len(values) - 1
    probes = 0
    while high >= low:
        middle = (low + high) // 2
        probes += 1
        value = values[middle]
        if value == target:
            return middle, probes
        if target > value:
            low = middle + 1
        else:
            high = middle - 1
    return None, probes

{| class="wikitable"

! Probe !! Low !! High !! Middle index !! Middle value !! Action |- | Start || 0 || 3 || 1 || 4 || Seven is greater, so low becomes 2 |- | Second probe || 2 || 3 || 2 || 7 || Equal, so return index 2 |} For target seven in two-four-seven-nine, start with low zero and high three. The lower middle index is one, containing four. Seven is greater, so low becomes two. The next middle is index two with seven; return index two and two probes. A convention choosing an upper middle could produce another valid trace. State the convention before comparing exact steps instead of treating every different trace as wrong.

The required transfer list is three, six, nine, twelve, fifteen, eighteen, twenty-one. Target twelve is the first middle value at index three, so it takes one probe. Target eighteen visits twelve then eighteen, requiring two. Absent ten visits twelve, six and nine, then the updated low exceeds high and the function returns None after three probes. Explain each discarded interval; do not merely guess the final index.

With duplicate values, this particular binary search returns whichever equal middle it encounters, not necessarily the first occurrence. On two-two-two, it returns index one, while linear_search returns index zero. Both identify a matching value under their stated contracts. Requiring the first match would mean changing the binary algorithm and its tests, not asserting that the existing function already does so.

Harvard CS50's original binary-search short supplies a visual explanation. Compare its range convention and assumptions with our explicitly stated lower-middle Python implementation. The original traces and exercises here are independently authored; the written route remains complete without video. Original: CS50, Binary Search - CS50 Shorts. The written explanations and native tasks work without sound or the external player. The function shown checks type, range and ascending order on every call before its binary-search loop. Those safety checks are not included in the returned probe count and can require linear work. Consequently the complete checked function must not be advertised as logarithmic-time overall merely because its inner search repeatedly halves the range. A system that validates a protected sorted collection once and reuses it can amortise that preparation, but then must keep the collection ordered when it changes.

The search-loop model assumes quick access to a middle index, as Python lists provide. Finding a physical middle book by walking down a shelf or navigating a linked sequence has other costs. A smaller count of probes in one toy example does not prove shorter wall-clock time, superiority on unsorted data or a universal choice for every storage structure. State what was counted and the context of the decision.

Trace bubble-sort passes and compare total work

Sorting creates order but has a cost of its own. The original bubble-sort variant compares adjacent values and swaps them only when the left one is greater. Each completed left-to-right pass moves a largest remaining value to the end of the unsorted range. The next pass shortens that range. If a complete pass makes no swaps, the algorithm stops early. This precise variant determines the counts below; other bubble-sort implementations may keep comparing a longer range.

def bubble_sort(values):
    check_values(values)
    result = values.copy()
    comparisons = 0
    swaps = 0
    passes = []
    for end in range(len(result) - 1, 0, -1):
        swaps_this_pass = 0
        for index in range(end):
            comparisons += 1
            if result[index] > result[index + 1]:
                result[index], result[index + 1] = result[index + 1], result[index]
                swaps += 1
                swaps_this_pass += 1
        passes.append(result.copy())
        if swaps_this_pass == 0:
            break
    return result, comparisons, swaps, passes

{| class="wikitable"

! Stage !! List state !! Cumulative adjacent comparisons !! Cumulative swaps |- | Original || 4, 1, 3, 2 || 0 || 0 |- | Pass 1 || 1, 3, 2, 4 || 3 || 3 |- | Pass 2 || 1, 2, 3, 4 || 5 || 4 |- | Pass 3 || 1, 2, 3, 4 || 6 || 4 |} Start with four, one, three, two. In the first pass compare four with one and swap, then four with three and swap, then four with two and swap. The resulting list is one, three, two, four: three comparisons and three swaps. Pass two compares one with three without a swap, then three with two and swaps; now the list is one, two, three, four, with five comparisons and four swaps in total. The last one-comparison pass makes no swaps and confirms early termination, giving six comparisons and four swaps overall.

The list becoming sorted after pass two does not mean this implementation performed no third pass. It needs its announced no-swap confirmation. Already sorted one-two-three-four takes one pass, three adjacent comparisons and zero swaps. Reverse four-three-two-one takes six comparisons and six swaps. Empty and one-item lists need no adjacent comparisons and produce no pass snapshots. Equal items are not swapped by the strict greater-than test.

Harvard CS50: Bubble Sort. Compare adjacent swaps and early stopping with the exact shrinking-range variant and original trace taught here.

The function copies its integer list before sorting, preserving the input and its order. Each recorded pass is another shallow copy of a flat list of integers, so later passes do not rewrite previous snapshots. This preservation claim concerns this implementation and these data; sorting records would require a defined key and moving the complete record, while nested mutable objects need additional copying care.

For a one-off search of an unsorted four-item list, simple linear search may be the sensible choice. Sorting solely to permit one binary search adds work and changes positions. For many searches of an already maintained ordered collection, halving the search range can reduce search probes substantially. Growing input size affects the shapes differently: linear search may examine every item, binary-search probes grow by roughly one for each doubling, and this bubble-sort variant has at most the triangular number of adjacent comparisons. This is a reasoned operation-count model, not a measured timing benchmark.

The exact original functions were actually tested on many short lists, duplicate and absent targets, all permutations of distinct small lists, and empty, boundary and malformed inputs. Compare sorted results with an independent reference, preserve counts and record the unchanged source. For a practical portfolio, submit complete traces for both searches, each bubble-sort pass, an explicit cost unit and at least two justified method choices. Do not infer that an online quiz certifies practical implementation or the full breadth of KS3 algorithms.

Interactive Tasks

Quiz: Test Your Knowledge

What does linear search for seven inspect in four-two-seven-nine? (Four, then two, then seven for three probes) (!Only the middle item because linear means halving) (!All four values even after the first match is found) (!Nothing because every search requires sorted input)

What precondition justifies discarding half a binary-search range? (Ascending order under the same comparison rule) (!The list having a visually tidy screenshot) (!The target being a positive number) (!Having fewer than ten values regardless of order)

What is the first middle value for seven in sorted two-four-seven-nine under our convention? (Four at index one) (!Seven at index two) (!Two at index zero) (!Nine at index three)

How many probes find twelve in three-six-nine-twelve-fifteen-eighteen-twenty-one? (One because twelve is the first middle value) (!Seven because every algorithm must read every item) (!Four because twelve has four letters in a label) (!Zero because index zero always means not found)

What does this binary search return on two-two-two with target two? (The middle matching index one) (!Always the first matching index zero) (!None because duplicate values make ascending order impossible) (!All matching indexes as a new list)

What follows the first bubble-sort pass on four-one-three-two? (One-three-two-four after three adjacent swaps) (!One-two-three-four with no comparisons) (!Four-three-two-one after one exchange) (!One-four-three-two as the complete finished pass)

Why does the original four-item bubble example perform a third pass? (Its stated variant confirms a no-swap pass before stopping) (!Every sorted list must be deliberately reversed once) (!The source list was overwritten by the search function) (!A third pass changes the target into a different value)

What does the reported binary-search probe count exclude? (The validation and ascending-order checks before its search loop) (!Every middle value inspected by the search loop) (!The successful matching probe) (!All unsuccessful searches by definition)

What can happen to indexes after sorting a copy? (A value may move to a different position from the original) (!Every original index is guaranteed unchanged) (!All values necessarily become unique) (!The target always moves to index zero)

What is a justified method comparison? (State data assumptions, preparation work and the operation being counted) (!Declare binary search universally faster from one small example) (!Treat comparison counts as measured seconds on every device) (!Ignore sorting cost whenever input is originally unsorted)

Memory Game

Linear search	Inspect items in order until a match or the end
Binary search	Narrow a sorted search interval using its middle
Precondition	An assumption that must hold before the method is used
Probe	One search item inspection under the stated count
Bubble sort	Compare adjacent items and swap an out-of-order pair
Sorted-copy index	A position that may differ from the original record position

Drag and Drop

An unsorted list is offered to binary search	Establish correct ascending order or choose another method
A search returns index zero	Treat it as a valid first-position match rather than false failure
Two middle positions are possible	State and consistently apply a lower- or upper-middle convention
A sorted copy changes record positions	Preserve identities if original-row positions are required
A one-off query needs a previously unsorted list	Include preparation work when deciding whether sorting is worthwhile

Crossword Puzzle

LINEAR	What search method inspects items sequentially?
BINARY	What search method halves a sorted interval?
MIDDLE	What part of the current interval is inspected next?
PROBE	What counted action inspects one search item?
BUBBLE	What adjacent-swap sorting method is taught?
INDEX	What identifies a position in a list?

LearningApps

Optional extra practice. Choose an appropriate activity with your teacher. If the external collection is unavailable, use the native activities and independent tasks in this course.

Cloze Text

Open Tasks

Easy

Trace a sequential search: Find seven, four and absent twelve in four-two-seven-nine and count probes.
Explain sorted order: Give a reason why binary-search elimination needs ascending values.
Follow the middle: Trace target seven in two-four-seven-nine using the stated lower-middle convention.
Perform a first pass: Show all three adjacent comparisons and swaps for four-one-three-two.

Standard

Complete the transfer search: Trace twelve, eighteen and absent ten in the seven-item transfer list with explicit low, high and middle.
Compare duplicate contracts: Use two-two-two to explain the different returned matching indexes of the two functions.
Complete bubble sorting: Record every pass and cumulative comparison and swap count for four-one-three-two.
Compare honest costs: Compare one-off unsorted search with repeated ordered searches, stating preparation and count exclusions.

Advanced

Test complete implementations: Run normal, empty, duplicate, absent, malformed and boundary cases against independent expectations, preserving source lists.
Expose a misleading claim: Explain why the complete checked binary function is not logarithmic overall merely because its inner search is.
Preserve identities: Design a record-key sort that can map a found sorted row back to its original identifier without assuming unchanged indexes.
Evaluate variants: Compare early-stop and fixed-pass bubble variants using exact conventions; distinguish operation counts from any actual device timing experiment.

Learning Check

Linear search and returned meaning: Trace the original unsorted case.
Binary range and transfer: Apply the exact lower-middle convention.
Preconditions,duplicates and identities: Explain what the returned index does and does not promise.
Bubble-sort trace: Explain every required pass and count.
Comparison and preparation: Avoid a false speed conclusion.
Tests and practical evidence: Produce a reproducible algorithm portfolio.

Worked checks and assessment guidance

For seven in four-two-seven-nine, the first three probes inspect four,two and seven,returning index two and count three. Four returns index zero and one probe;absent twelve returns None and four probes. Empty input returns None and zero. Index zero is a valid result and must not be treated as failure by ordinary truthiness. The target contract is an integer and the helper rejects malformed list data.
For sorted two-four-seven-nine,target seven first inspects index one with four,then index two with seven,so two probes. In three-six-nine-twelve-fifteen-eighteen-twenty-one,target twelve is the first middle and takes one probe;eighteen visits twelve then eighteen;absent ten visits twelve,six,nine before the interval becomes empty. Move an endpoint past the inspected middle so progress is guaranteed.
Binary search requires ascending order under its comparison rule and the checked implementation rejects unsorted data. Its two-two-two case returns middle index one,not necessarily the first duplicate;linear search returns zero. Sorting a copy may change positions,such as four moving from original index zero to sorted index one in the four-two-seven-nine example. Preserve original row identities if a caller needs that mapping.
Four-one-three-two becomes one-three-two-four after three comparisons and three swaps. Pass two makes two comparisons and one swap,giving one-two-three-four with five comparisons and four swaps cumulatively. A final one-comparison,no-swap pass brings total comparisons to six and confirms stopping. Sorted four-item input needs three comparisons and zero swaps;reverse input needs six and six. Counts depend on the precise shrinking-range,early-stop variant.
Search probes count item inspections in the search loop,not every Python comparison or validation step. This checked binary function validates values and ascending order each call,so its total work is not logarithmic overall. Sorting a one-off unsorted list adds work;maintained ordered data can make repeated binary searching useful. Middle access cost,data size,updates and preparation all affect the method choice. No wall-clock benchmark was measured by these count examples.
Compare outputs with independent membership,first-index where promised,and sorted references. Check duplicates,empty collections,absent targets,range/type failures and unchanged inputs. Bubble-sort output must preserve the original multiset and earlier pass snapshots. Submit actual runs plus full search and sorting traces and at least two reasoned method choices. Paper predictions and online quiz success do not alone establish practical programming competence or the full breadth of KS3 algorithms.

Learning evidence

Submit complete linear and binary-search traces with the exact middle convention, a full bubble-sort pass table, runnable original or equivalent functions and actual expected-versus-observed tests. State sorted-data assumptions, duplicate/index contracts, count units and preparation costs. Preserve original values and identities; distinguish a paper trace from executed practical evidence.

OER and Wikipedia

Original checked Python algorithms,examples,traces,count conventions,tests and assessments. Harvard CS50 algorithm notes and the original binary-search and bubble-sort shorts provide supporting algorithm explanations;no source code or lecture exercise is reproduced. DfE Computing programme of study, KS3 algorithm comparison. Year 8 sequencing is editorial. Primary sources checked 14 November 2026 local time. Both embedded videos identify original publisher CS50. The Commons photograph and library context retain exact credits and do not claim to depict the original algorithms or certify sorted data.

Python Code.jpg, Weal2019, CC0. Unchanged original; caption and learning activities are original.

International books at Kent Library.jpg, Roc0ast3r, CC0. Unchanged original; caption and learning activities are original.