aiMOOC

Algorithms and computational efficiency for AI tasks - AI Year 10

QR-Code

Introduction

Animated binary search narrowing an ordered interval to find a target — Watch the interval shrink. The animation uses a different small example from our executed sixteen-key trace; the written table gives a motion-independent explanation.

Choose a method because it is correct for the input and suitable for the complete task, not because one demonstration looked quick. Trace linear and binary search on the same sixteen sorted keys, inspect merge sort, and separate search probes from validation, sorting, memory and measured time. The complete original Python lab was executed on synthetic integer keys. It trains no model and performs no live learner-data lookup.

Bridge: a list is an ordered sequence of stored values, an index locates a position starting at zero, and a target is the value sought. Binary search needs a list ordered by the same comparison key used in the search. Review modular input contracts and number representation if needed; no optional earlier AI course or external account is assumed.

Trace two searches on the same ordered keys

Searching asks whether a target occurs and, under our contract, returns a matching index or an explicit missing result. Linear search visits positions from the beginning and stops at the first equal value. It can work on unsorted input because it does not discard unvisited regions based on their values. If the target is last, or absent, it can inspect every element. A quick success at the first position tells us little about the worst-position or missing cases.

Use the original source fixture: sixteen sorted integers from one through sixteen, with target sixteen. Linear search examines values one, two and so on through sixteen. It returns index fifteen after sixteen probes. A probe here means one visited list element whose value is compared with the target. It is not a claim of one machine instruction, one Python comparison operator, one second or a complete computational cost.

Binary search maintains an inclusive candidate interval from low to high. Select the middle index by adding low and high, dividing the sum by two and rounding down. If the middle value equals the target, return that matching index. If the target is larger, discard the middle and everything below it by setting low to mid plus one. Otherwise set high to mid minus one. Ordering justifies discarding that region; without the precondition the same decision can lose a target that is present.

Probe	Low	High	Middle index	Value	Decision for target sixteen
1	0	15	7	8	Keep indexes eight through fifteen
2	8	15	11	12	Keep indexes twelve through fifteen
3	12	15	13	14	Keep indexes fourteen through fifteen
4	14	15	14	15	Keep index fifteen
5	15	15	15	16	Return index fifteen

The executed binary search therefore uses five search probes for this target, compared with sixteen for linear search. Five includes the final equality check. Saying that sixteen items can simply be halved four times does not automatically count the final successful probe under this implementation. Off-by-one assumptions must be resolved by the actual loop and trace.

CS50's Binary Search short supports the interval idea. Compare the general demonstration with the original table rather than assuming it uses the same values or middle-index convention. Our written explanation supplies the required method without playback or animation.

Boundary tests change the conclusion. For target one in the same list, linear search takes one probe while our binary search takes four. For missing target seventeen, linear search takes sixteen and binary search takes five before the interval becomes empty. An empty list returns missing with zero probes for either algorithm. No list element should be read when low is greater than high.

Duplicates require a declared result. For the list two, two, two and target two, our linear search returns index zero and binary search returns index one. Both find a matching value, but binary search is not specified to return the first occurrence. If the application needs every occurrence or the leftmost one, change the contract and test that behaviour rather than calling this permitted difference a failure.

Trace first: find target eight in one through sixteen, then target zero. Hint: use the middle value and state the remaining interval after every decision. Partial check: eight is at index seven and is found on the first binary probe. Missing zero repeatedly moves the upper bound left. Count visited values, not the number of characters in the written trace.

Sort before searching and account for preparation

An unsorted list cannot be made safe for binary search by calling the function with an optimistic name. Our bounded wrapper validates exact integer types and rejects a descending adjacent pair. On a valid sixteen-key list it checks fifteen adjacent pairs before searching. Those ordering checks are separate from the five search probes. The full Python call also performs type checks and other operations. It is therefore wrong to claim that the entire call costs only five operations or is sixteen divided by five times faster.

If the data is already kept ordered by a trusted maintained invariant, a carefully designed system might avoid repeated full order checks. That would be a different interface with a different responsibility. We do not silently remove validation from the teaching program. If the data changes, an old sorting guarantee may no longer apply. Any decision to reuse an ordered structure must include how updates preserve its order.

Merge sort supplies a useful preparation method. Split the input into halves until the pieces contain zero or one element. Such a piece is already ordered. Merge two ordered pieces by comparing their first remaining values, moving the smaller into a new output, and repeating until one piece is exhausted. Then append the remaining values from the other piece. The important precondition is that each piece entering a merge is already ordered; merely alternating items from two lists is not sufficient.

Animated merge sort splitting a list into small pieces and merging them into ascending order — The external animation illustrates splitting and merging. Its eight-value fixture differs from our original program; the text traces our own merge results.

Our original unsorted fixture is nine, one, seven, three, five, two, eight, four. The left half becomes one, three, seven, nine; the right half becomes two, four, five, eight. Merge those halves by choosing one, two, three, four, five, seven and eight in turn; nine is the final unopposed remainder. The final list is one, two, three, four, five, seven, eight, nine. Sorting must preserve every original value and multiplicity, not invent the missing value six.

Original ordered pieces entering a merge	Output
Nine and one	One, nine
Seven and three	Three, seven
One, nine with three, seven	One, three, seven, nine
Five and two	Two, five
Eight and four	Four, eight
Two, five with four, eight	Two, four, five, eight
One, three, seven, nine with two, four, five, eight	One, two, three, four, five, seven, eight, nine

The executed merge sort reports seventeen comparisons between the current left and right key values across all merges. Appending an unopposed remainder is not counted as another key comparison. This counter excludes list allocation, copying, slicing, loop tests and recursive calls, so it is not a complete instruction count or time measurement. Trace logs themselves consume additional memory. Our implementation also creates intermediate lists; memory and copying matter when comparing real implementations.

CS50's Merge Sort short gives an additional explanation of split and merge. Use the complete written trace to check that a merge maintains order and preserves duplicates. Neither the animation nor the video is evidence that your own code or a real AI pipeline was executed correctly.

After sorting the original eight keys, searching for eight takes three binary search probes and the wrapper also performs seven adjacent ordering checks. A one-off unsorted lookup could instead use linear search without preparing an ordered copy. Many lookups on a maintained ordered collection may justify preparation, but the number of queries, update frequency, memory and comparison costs matter. Do not infer the best end-to-end method from a single small trace or a counter that excludes preparation.

Attempt before checking: merge the sorted pieces one, five and two, three, six. Hint: compare only the two current front values. Partial check: choose one, then two, then three. When the left piece is exhausted after choosing five, append six. Explain how the remainder rule avoids losing values without claiming that the remainder needs no copying work.

Execute the lab and choose a suitable complete method

The complete original program below produces the source searches, empty and duplicate boundaries, a merge trace and the sorted lookup. It accepts at most 256 exact integer keys between minus ten thousand and ten thousand. Booleans, missing entries, floating-point values and strings are outside this particular contract. A different application might support other ordered types, but it must define that interface and its comparison rules explicitly.

"""Bounded original search traces and merge-sort comparison counts, not timing."""
import json


def checked_values(values):
    if not isinstance(values, list) or len(values) > 256:
        raise ValueError("Expected at most 256 integer keys")
    if any(type(v) is not int or not -10000 <= v <= 10000 for v in values):
        raise ValueError("Expected exact bounded integer keys")


def checked_target(target):
    if type(target) is not int or not -10000 <= target <= 10000:
        raise ValueError("Expected a bounded integer target")


def linear_search(values, target):
    checked_values(values)
    checked_target(target)
    visited = []
    for index, value in enumerate(values):
        visited.append(index)
        if value == target:
            return dict(index=index, probes=len(visited), visited=visited)
    return dict(index=None, probes=len(visited), visited=visited)


def binary_search(values, target):
    checked_values(values)
    checked_target(target)
    if any(values[i] > values[i+1] for i in range(len(values)-1)):
        raise ValueError("Binary search requires nondecreasing keys")
    low, high = 0, len(values)-1
    trace = []
    while low <= high:
        mid = (low + high) // 2
        value = values[mid]
        trace.append(dict(low=low, high=high, mid=mid, value=value))
        if value == target:
            return dict(index=mid, probes=len(trace), trace=trace, ordering_checks=max(0,len(values)-1))
        if target > value:
            low = mid + 1
        else:
            high = mid - 1
    return dict(index=None, probes=len(trace), trace=trace, ordering_checks=max(0,len(values)-1))


def merge_sort(values):
    checked_values(values)
    comparisons, merges = 0, []

    def sort_part(part):
        nonlocal comparisons
        if len(part) <= 1:
            return part[:]
        mid = len(part) // 2
        left, right = sort_part(part[:mid]), sort_part(part[mid:])
        out, i, j = [], 0, 0
        while i != len(left) and j != len(right):
            comparisons += 1
            if left[i] <= right[j]:
                out.append(left[i])
                i += 1
            else:
                out.append(right[j])
                j += 1
        out.extend(left[i:])
        out.extend(right[j:])
        merges.append(dict(left=left, right=right, result=out[:]))
        return out

    result = sort_part(values)
    return dict(values=result, key_comparisons=comparisons, merges=merges)


def demonstrate():
    values = list(range(1,17))
    unsorted = [9,1,7,3,5,2,8,4]
    sorted_report = merge_sort(unsorted)
    return dict(source_values=values, target=16,
                linear=linear_search(values,16), binary=binary_search(values,16),
                missing_linear=linear_search(values,17), missing_binary=binary_search(values,17),
                first_linear=linear_search(values,1), first_binary=binary_search(values,1),
                empty_linear=linear_search([],1), empty_binary=binary_search([],1),
                duplicate_linear=linear_search([2,2,2],2), duplicate_binary=binary_search([2,2,2],2),
                unsorted_values=unsorted, sorted_report=sorted_report,
                sorted_lookup=binary_search(sorted_report["values"],8),
                wall_clock_measured=False, model_trained=False, synthetic_keys=True)


if __name__ == "__main__":
    print(json.dumps(demonstrate(), indent=2))

Inspect the printed evidence rather than asserting that an algorithm name guarantees success. Linear and binary search agree about membership on the valid ordered source fixture and both return index fifteen for sixteen. The duplicate case shows that their permitted matching indexes can differ. The merge output is ordered and preserves the original values. Tests of empty input, missing keys and incompatible types distinguish a valid missing result from an invalid request.

A trace can diagnose a precise defect. Consider a deliberately incorrect instruction: when target sixteen is greater than middle value eight, set high to mid minus one. Its first decision keeps indexes zero through six and immediately discards the true target at index fifteen. The first divergence occurs in that branch, before a later missing result. The minimal conceptual correction is to set low to mid plus one for a larger target. This is a labelled counterexample trace; the executed program already contains the correct branch and was not run with a hidden broken version.

Make a test log with input provenance, precondition, expected membership and allowed matching index, actual result, visited positions, error category and limitation. Test normal targets, the first and last positions, values outside the range, empty input, duplicates and an unsorted list. If unsorted input is rejected, record a validation rejection rather than a false claim that the target was absent. A search that returns missing on invalid data can otherwise look successful while answering the wrong question.

For an AI-adjacent task, these algorithms could locate a synthetic numeric record key in an approved dataset or order a declared scalar feature for later processing. Searching for an exact ordered key is different from semantic retrieval, image recognition or nearest-neighbour search across many dimensions. A binary search over numeric keys does not understand a sentence or train a predictor. Check the data dictionary and the actual required result before applying a familiar method.

Transfer to an invented community equipment catalogue with numeric item keys. If the catalogue is small and unsorted and only one item is needed, a linear scan can be appropriate. If many queries target a mostly unchanged collection, an ordered maintained structure may support binary lookup. If sorting changes positions, an index in the sorted copy is not automatically the original record position; keep a valid key-to-record mapping. Duplicate keys need a defined policy before using the returned match to identify an item.

Measure any real performance claim separately. State the operation counted, input distribution, input sizes, preparation included, memory constraints and repeated-run method. A wall-clock benchmark would need actual measured runs on a named setup, and variation should be reported. This lab records logical probes and selected key comparisons; it measures no wall-clock time and makes no hardware-speed claim. Common GCSE content asks for reasoned fitness for purpose, not a formal proof of asymptotic efficiency.

Your decision: compare a one-off lookup in eight unsorted keys with two hundred lookups in a maintained sixteen-key list. State which method you would investigate, which assumptions differ, and what total cost evidence remains necessary. Hint: distinguish preparing an ordered collection from searching it, and treat validation as work. Partial check: a single favourable binary trace cannot establish the full repeated-query system's time or maintenance cost.

Interactive Tasks

Quiz: Test Your Knowledge

What must hold for the demonstrated binary search? (Keys are ordered nondecreasingly under the search comparison) (!Keys are randomly shuffled before every probe) (!Every key is a different positive number) (!The target is guaranteed to be present)

What index contains sixteen in the source list one through sixteen? (15) (!16) (!0) (!7)

How many search probes does the demonstrated binary search use for sixteen? (5) (!4) (!16) (!1)

How many probes does linear search use for the first value one? (1) (!4) (!15) (!16)

What do both searches return for a valid empty list? (A missing result with zero probes) (!The first index with one probe) (!An invented matching value) (!The final element)

Why can two matching indexes differ on duplicate keys? (The algorithms have different permitted match positions) (!Binary search always removes all duplicates) (!Linear search always returns the last occurrence) (!Duplicates make every search meaningless)

What must merge sort preserve as well as ordering? (Every input value and its multiplicity) (!Only values above the target) (!Only one copy of every value) (!The original position of every integer)

What does the seventeen merge comparison count exclude? (Copying allocation and other non-key-comparison work) (!All comparisons between two current keys) (!The original input values) (!The final merge result)

What should the wrapper do with an unsorted binary-search input? (Reject the invalid precondition) (!Claim that the target is absent) (!Silently pretend it is sorted) (!Train a language model)

Which conclusion does the lab support? (Logical traces and selected counts for the tested synthetic inputs) (!A measured speed advantage on every computer) (!Certified performance of a production AI model) (!Proof that one algorithm is always best)

Memory Game

Search	Find a permitted match or report missing
Probe	Inspect one list element during the search
Precondition	A requirement that must hold before the method
Interval	The current candidate index range
Merge	Combine two ordered pieces into one ordered output
Multiplicity	How many copies of a value are present

Drag and Drop

Unsorted one-off lookup	Linear search can avoid sorting preparation
Ordered candidate interval	Binary search can discard a justified region
Empty valid input	Return missing without reading an element
Duplicate-key contract	State which matching occurrence is acceptable
End-to-end comparison	Include validation preparation queries updates and memory

Crossword Puzzle

LINEAR	Search that visits positions in sequence
BINARY	Search that narrows an ordered interval
MERGE	Combine two already ordered pieces
PROBE	One inspected search element
INTERVAL	Candidate range from low to high
CONTRACT	Declared inputs outputs and permitted behaviour

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

Linear search can work on

keys. Binary search requires a suitable

. The candidate range is an

. The source target sixteen is found at index

. The demonstrated binary method uses five search

. The order-check work is counted

. Merge sort first splits then

. A valid empty search reports

. Duplicate keys require a declared

. Sorting can change a record's

. The lab measures no wall-clock

. A real performance claim needs additional

.

Open Tasks

Easy

Trace sixteen in sequence: List the positions visited by linear search for sixteen in one through sixteen. Explain the index and probe count.
Trace the binary interval: Complete low high mid and middle-value rows for the binary search for sixteen. Explain each discarded region.
Test empty input: Explain both missing results and zero probes for an empty list. Distinguish valid emptiness from a missing or invalid container.
Merge two ordered pieces: Merge one five and two three six, recording each comparison and the unopposed remainder.

Standard

Compare first last and missing: Compare search probes for one sixteen and missing seventeen in the same ordered list. State the unit counted and excluded work.
Interpret duplicate matches: For two two two and target two, explain why indexes zero and one can both satisfy the current contract and when a leftmost contract would differ.
Check the merge fixture: Trace the original eight-key merge sort. Check order multiplicity the missing value six and the seventeen selected key comparisons.
Diagnose the first divergence: Trace the labelled wrong branch that lowers high when sixteen exceeds middle eight. Identify the first divergence and give the minimal conceptual correction.

Advanced

Compare complete query workloads: Compare one lookup on unsorted keys with repeated lookup on maintained ordered keys. Include validation preparation updates memory and allowed result requirements.
Design a boundary test matrix: Specify normal first last absent empty duplicate unsorted and invalid-type cases, expected results rejection categories and remaining limitations.
Transfer to an equipment catalogue: Define numeric keys mapping to records and duplicate policy for a fictional catalogue. Explain changes after sorting or updates and the checks needed.
Separate logical counts from time: Design a supervised performance investigation without inventing results. State distributions input sizes counted operations actual time measurements repetition and uncertainty.

Learning Check

Check the source two-search trace: Trace linear and binary search for sixteen in the sixteen ordered source values.
Check first missing and duplicate boundaries: Explain the results for one missing seventeen empty input and duplicate twos.
Check merge preservation and selected cost: Give the original eight-key sorted output and interpret the counter.
Locate a wrong-branch divergence: Diagnose setting high to mid minus one when the target is larger than the middle.
Choose a method for a complete workload: Choose and justify an investigation for one-off unsorted and repeated maintained-order catalogue lookup.
Design a bounded evidence log: Describe evidence and limits before using the method for an AI-adjacent dataset task.

Worked checks and assessment guidance

Linear search visits indexes zero through fifteen and uses sixteen probes. Binary search visits indexes seven eleven thirteen fourteen fifteen with values eight twelve fourteen fifteen sixteen, returning index fifteen after five probes. Its wrapper also performs fifteen adjacent ordering checks; these are separate from search probes.
For one, linear takes one probe and binary four. For missing seventeen, linear takes sixteen and binary five before returning missing. Empty valid input gives missing with zero probes. For two two two, linear returns zero and binary one; both are allowed matching indexes, while a first-occurrence requirement would need a different binary contract.
Nine one seven three five two eight four becomes one two three four five seven eight nine. The output has the same eight values and multiplicities; it must not add six. The original merge sort records seventeen comparisons between current left and right keys, excluding copying slicing allocation recursion and loop overhead. The subsequent lookup for eight uses three probes plus seven adjacent ordering checks.
At low zero high fifteen, mid seven contains eight. Target sixteen is larger, so reducing high to six discards its actual index fifteen immediately. Set low to mid plus one instead. This is a labelled counterexample trace; the executed code already uses the correct branch. Recheck boundaries and unsorted rejection instead of claiming one corrected trace proves every input.
A linear scan can suit a small unsorted one-off query without ordering preparation. Repeated queries on a maintained ordered collection can justify binary lookup, but include preparation validation updates comparison and memory costs. A sorted index must map correctly back to the record, and duplicate keys need a declared policy. No single probe count establishes end-to-end time.
Use synthetic or properly permissioned keys and a dictionary, record preconditions expected and actual membership allowed indexes visited positions errors and limitations. Test normal boundary duplicate absent invalid and update cases. Keep exact-key search separate from semantic or multidimensional similarity retrieval. Any speed claim requires actual stated-setup measurements and repeated-run variation; this executed lab supplies logical counts only.

Learning evidence

Keep both complete source traces, the first missing empty and duplicate boundaries, the labelled wrong-branch diagnosis and the original merge sequence. Verify order and value multiplicity. State the counting unit and excluded work, preserve actual program output and record rejected invalid requests separately from valid missing results. Add a complete-workload catalogue plan with key-to-record mapping updates and duplicate policy. Do not present an animation a small trace or selected operation counter as proof of measured production speed.

OER and Wikipedia

DfE GCSE Computer Science subject content, updated 31 March 2025, standard algorithms and fitness-for-purpose skills inspected 15 November 2026. The source requires binary search and merge sort; the particular AI-adjacent Year 10 sequence and fixtures are editorial. Formal efficiency comparisons are not a common-content requirement.

Harvard CS50 algorithm notes, linear search binary search and merge sort sections inspected 15 November 2026. The course uses an original Python implementation and independent fixtures, not copied lecture code or a claimed CS50 qualification. Python bisect documentation inspected for sorted-input and preparation distinctions; bisect locates insertion points, whereas our original function returns a matching index or missing. Do not treat them as identical APIs.

Binary-search-work.gif, Mazen Embaby, CC BY-SA 4.0, unchanged. Merge-sort-example-300px.gif, Swfung8, CC BY-SA 3.0, unchanged. Retained original animation bytes metadata and native rendering checked; beginning middle and end frames visually inspected. Their fixtures differ from the original source trace, which is fully available as text. Display resizing does not change the animation data.

https://www.youtube.com/watch?v=T98PIp4omUA — CS50: Binary Search - CS50 Shorts. https://www.youtube.com/watch?v=Ns7tGNbtvV4 — CS50: Merge Sort - CS50 Shorts. Verified metadata embedding availability and retained previews checked and visually inspected. External unchanged embeds imply no transcript copying endorsement or relicensing. Full methods remain in the written course.

All numeric source fixtures code tests logs counter definitions and community-catalogue scenarios are original teaching constructions. The program executes bounded algorithms without model training personal learner records or wall-clock benchmarking. Author checks are not independent expert certification.