01 | FIND ONE ITEM IN A COLLECTION

You have a pile of club sign-up cards and want to find the card for S205. You look at the first card. If it is not S205, you look at the next. You continue until you find the card or reach the end of the pile.

This is the idea behind linear search: check items one at a time, in order, comparing each with the value you want to find.

The value being searched for is called the target. The collection being searched contains the candidate values. A comparison asks whether the current item equals the target.

Linear search is also called sequential search. It can be used on an unsorted list because it does not depend on the values being in increasing, alphabetical or any other sorted order.

02 | UNDERSTAND THE LIST BEFORE THE ALGORITHM

We will search this collection of five student identifiers.

An array is a collection of items accessed using numbered positions called indexes. An element is one item in the array. In this example, the first index is 1 and the last is 5.

StudentIDs[3] means “the value at index 3”, which is S205. The index 3 and the stored identifier S205 are different pieces of information.

Some arrays use a first index of zero. Our example deliberately uses indexes 1 to 5, so the search and stopping condition must match that range. You will study arrays in more depth in Topic 8.

We assume the five array elements have already been supplied. This lesson concentrates on searching them, not on entering or loading the whole collection.

03 | THE BASIC STEPS OF LINEAR SEARCH

Start at the first item. Compare it with the target. If they match, report success. If they do not, move to the next item and repeat the comparison.

There are two reasons to stop: a matching item has been found, or every item has been checked without a match. In the second case, report that the target was not found.

A search that stops at the first match is an early-exit version. We use this version throughout the worked algorithm. Another design could scan the whole collection, but it would not stop at the same point.

The algorithm does not rearrange the identifiers. Searching finds whether or where a value exists; sorting changes their order. Keep those purposes separate.

04 | TRACE A SUCCESSFUL SEARCH

Search for S205. At index 1, the stored value is S104. It is not equal to S205, so move on. At index 2, S307 is also not equal to S205.

At index 3, the stored value is S205. The comparison is true, so the search succeeds and stops. It does not need to check indexes 4 and 5.

This search uses three element comparisons: one equality check for each of the first three array items.

The result can communicate both that a match exists and its position. Here the matching index is 3. Do not report 3 as the student identifier: it is the location of the identifier in this array.

05 | TRACE AN UNSUCCESSFUL SEARCH

Now search for S999 using the same unchanged array. None of the five identifiers equals the target, so every item must be checked.

After index 5 has been checked, there are no items left. The algorithm reports “Not found”. It must not try to read index 6 because this array only has indexes 1 to 5.

This search uses five element comparisons. It does not know that the item is absent until it has checked the entire collection.

Unsuccessful cases are important tests. An algorithm that works when a match is present may still run beyond the array when no match exists.

06 | GIVE EACH VARIABLE A CLEAR JOB

The pseudocode needs to remember where it is and whether it has succeeded.

Found is a Boolean, meaning it holds TRUE or FALSE. It starts FALSE because no match has yet been found.

Position tracks the next element to check. MatchIndex records the successful index separately. It starts at 0, which is outside our valid index range and represents “no matching position recorded yet”. Zero is not universally outside every array; it is suitable for this specific 1-based example.

These names make the roles visible. The algorithm would still work with short names, but clear names make it easier to explain and debug.

07 | READ THE COMPLETE PSEUDOCODE

The following algorithm assumes StudentIDs already contains the five displayed identifiers. Enter a target such as S205 or S999.

DECLARE StudentIDs : ARRAY[1:5] OF STRING
DECLARE Target : STRING
DECLARE Position : INTEGER
DECLARE MatchIndex : INTEGER
DECLARE ItemCount : INTEGER
DECLARE Found : BOOLEAN

// Assume StudentIDs already contains the five identifiers
ItemCount ← 5
INPUT Target
Position ← 1
MatchIndex ← 0
Found ← FALSE
WHILE Position <= ItemCount AND NOT Found DO
    IF StudentIDs[Position] = Target
      THEN
        Found ← TRUE
        MatchIndex ← Position
      ELSE
        Position ← Position + 1
    ENDIF
ENDWHILE
IF Found
  THEN
    OUTPUT "Found at index ", MatchIndex
  ELSE
    OUTPUT "Not found"
ENDIF

The loop condition requires both that Position is within the array and that a match has not yet been found. On a match, Found becomes TRUE and MatchIndex records the position. On a mismatch, Position increases by one.

After the loop, the IF statement chooses the correct output. The array itself is unchanged.

The separate MatchIndex makes the result explicit: a failed search does not accidentally output the out-of-range Position reached after the final mismatch.

08 | EXPLAIN THE CONDITION ONE PART AT A TIME

Position <= ItemCount checks whether there is still an element available. NOT Found is true while Found is FALSE. AND means both must be true for another repetition.

After finding S205, Found is TRUE. NOT Found is therefore false, so the loop ends even though Position is still within the array.

After five mismatches, Position becomes 6. Position ≤ ItemCount is false, so the loop ends even though Found is still FALSE.

The condition checks the bounds and the flag only. The array element is read inside the body after the bounds condition allows entry. This avoids relying on a language skipping an unsafe array access inside a compound condition.

WHILE is a pre-condition loop: it checks before each repetition. This is useful because a search should not access an element when no valid position remains.

09 | FOLLOW THE VARIABLES DURING EXECUTION

For target S205, Position begins at 1, Found is FALSE and MatchIndex is 0.

On the third comparison, Found changes to TRUE and MatchIndex becomes 3. Position does not increase on this branch. The next loop condition fails because NOT Found is false.

For target S999, Found never changes. Each mismatch increases Position, eventually producing Position 6. The next condition fails on the bound, and the output branch reports “Not found”.

Follow the final condition check as well as the body. A loop finishes because its condition no longer permits another repetition, not simply because the page has run out of instructions.

10 | WHAT IF THE TARGET APPEARS MORE THAN ONCE?

Suppose the array instead contains S104, S205, S307, S205 and S412. The target S205 occurs at indexes 2 and 4.

Our early-exit algorithm finds index 2 and stops. It reports the first matching index in the search order, not every matching index.

If the requirement is to find all occurrences, the design must change. Continue through every element and report or store each matching index. If the requirement is to count occurrences, increase a counter for each match instead of stopping at the first.

Do not assume one search result proves that a target occurs only once. The behaviour depends on the stopping rule and the system’s requirements.

11 | BEST AND WORST CASES

With a non-empty array, the best case for this early-exit search is a match at the first item: one element comparison is enough.

The worst case checks every item. This happens when the target is absent or when its first occurrence is the last element. For five items, that means five equality comparisons.

For a collection of N items, the worst case uses N element comparisons. Doubling the number of items can therefore double the number of comparisons required in the worst case.

Here we are counting comparisons between an element and the target, not every condition check, assignment or instruction. State what is being counted when explaining efficiency.

Linear search is straightforward and does not require sorted data. For very large collections it may require many checks. Other search methods exist, but are outside the standard search method required in this syllabus section.

12 | FIND THE COMMON ERRORS

Starting at the wrong index: starting Position at 0 in our 1-to-5 array attempts an invalid access. Starting at 2 skips the first item.

Using Position < ItemCount: this stops before checking index 5. A target in the last position would incorrectly appear absent.

Forgetting the increment: after a mismatch, the algorithm keeps checking the same element. If Found remains FALSE and the position stays valid, the loop does not reach its intended exit.

Resetting Found inside every repetition: this can destroy the stopping information. Initialise it before the loop and update it only when the algorithm finds a match.

Reporting failure too early: one mismatch does not mean the whole array lacks the target. Report failure after the search has finished without a match.

13 | TEST MORE THAN THE EASY MIDDLE MATCH

A useful test set includes the first element, a middle element, the last element and an absent target. Each exercises a different aspect of the search.

A duplicate test checks the promised first-match behaviour. If you later adapt the algorithm to a variable-length collection, also consider an empty collection: with ItemCount 0 and Position 1, the body should run zero times and report failure.

The fixed worked example has five items. Supporting empty collections or different lengths requires the collection representation and ItemCount to match that broader design.

When testing, compare the reported position, success/failure output and number of element comparisons with the expected results. Also confirm that searching has not changed the stored identifiers.

14 | EXPLAIN THE METHOD WITH REASONS

A clear description is: “Linear search compares each item with the target in order, stopping when a match is found or when every item has been checked.”

For an explain question, connect the steps to their purpose: “Position increases after a mismatch so the next comparison checks a new element. The upper-bound condition prevents access beyond the collection. Found stops further comparisons once a match has been located.”

If asked about unsorted data, explain that every candidate can be checked individually; the method does not use a sorted order to eliminate part of the collection.

You should now be able to trace a search, distinguish an index from a value, explain both exit conditions and identify common errors. The next lesson changes the collection’s order using bubble sort.