OCR J277 · Component 2 · Topic 2.1.3a

Searching Algorithms
Linear Search

Apply · Trace · Pseudocode · Efficiency

CSZone OCR GCSE Computer Science J277

Learning Objectives

By the end of this video you will be able to...

Describe how a linear search works in plain English — including what happens when the target is found and what happens when it is not present in the list

Write and identify linear search pseudocode — recognise its structure in unfamiliar code, identify the key components (loop, comparison, found flag), and trace it correctly

Apply linear search to a given data set — show every comparison made, state the number of comparisons needed, and give the correct result (index or "not found")

Complete and interpret trace tables for linear search — including both found and not-found cases, tracking the index variable, current value, and found flag at every step

State the best, worst, and average case efficiency of linear search in terms of number of comparisons, and explain the key advantage: it works on both sorted and unsorted data

⚡ "Apply algorithm to a data set" is directly on the spec — expect at least one linear search question on every Component 2 paper.

Linear Search — The Concept

What is a linear search?

DEFINITION

A linear search checks each element of a list one at a time, from start to end, comparing each value to the target. It stops as soon as the target is found, or reports "not found" once the entire list has been checked without a match.

KEY PROPERTIES

Works on sorted OR unsorted data — no prerequisite

Simple to understand and implement — very few lines of code

Checks elements sequentially — never skips ahead

THE PROCESS IN PLAIN ENGLISH

1.

Start at the first element (index 0)

2.

Compare the current element to the target value

3.

If it matches → target found, record the position

4.

If it doesn't match → move to the next element and repeat

5.

If the end is reached without a match → output "not found"

VISUAL EXAMPLE — searching for 9 in this list

3

7

2

9

4

1

8

0

1

2

3 ✓

4

5

6

Checked 3 → no. Checked 7 → no. Checked 2 → no. Checked 9 → YES. Found at index 3. Remaining elements (4, 1, 8) are never checked — the search stops immediately.

⚡ The biggest advantage of linear search is that it requires no prerequisite. Binary search only works on sorted data — linear search works on anything. In the exam, if asked to choose between them and the data is unsorted, the answer is always linear search.

Linear Search — Pseudocode

Linear search in pseudocode

STANDARD VERSION — FOR LOOP

// Array: data[], target to find found = FALSE FOR i = 0 TO LEN(data) - 1 IF data[i] == target THEN OUTPUT "Found at index: ", i found = TRUE END IF NEXT i IF found == FALSE THEN OUTPUT "Not found" END IF

ANATOMY OF THE CODE

found = FALSE — the flag. Set before the loop. Flips to TRUE when the target is found.

FOR i = 0 TO LEN(data)-1 — visits every index. LEN gives the number of elements.

data[i] == target — the comparison. Square brackets for array access.

Final IF after the loop handles the not-found case — only triggers if flag never flipped.

EARLY-EXIT VERSION — WHILE LOOP

// Stops as soon as target found i = 0 found = FALSE WHILE i < LEN(data) AND found == FALSE IF data[i] == target THEN found = TRUE ELSE i = i + 1 END IF END WHILE IF found THEN OUTPUT "Found at index: ", i ELSE OUTPUT "Not found" END IF

The WHILE version exits the loop the moment the target is found, rather than continuing through the remaining elements. The FOR version is simpler and more common in exam answers.

⚡ OCR will NOT ask you to write the full pseudocode from memory. But you must be able to identify a linear search from given code — look for: a loop through every element, a comparison to the target, and a found flag. Those three features together = linear search.

Applying Linear Search

Applying it — target found

THE LIST · TARGET = 9

3

7

2

9

4

1

8

0

1

2

3

4

5

6

i=033 == 9?✗ NO — move on

i=177 == 9?✗ NO — move on

i=222 == 9?✗ NO — move on

i=399 == 9?✓ MATCH — FOUND!

RESULT

Target 9 found at index 3

Comparisons made: 4 · Elements 4, 1, 8 never checked

KEY EXAM POINTS FROM THIS EXAMPLE

Number of comparisons = 4. Examiners often ask this — count each time you compare, including the final match.

The search stops immediately on finding the target — elements at index 4, 5, 6 are never visited.

The result is the index, not the value. The target is at index 3 (the value 9 is already known — they asked you to find where it is).

The list is unsorted — linear search doesn't care. Works perfectly.

Applying Linear Search

Applying it — target not found

THE LIST · TARGET = 5

3

7

2

9

4

1

8

0

1

2

3

4

5

6

i=033 == 5?✗ NO

i=177 == 5?✗ NO

i=222 == 5?✗ NO

i=399 == 5?✗ NO

i=444 == 5?✗ NO

i=511 == 5?✗ NO

i=688 == 5?✗ NO

End of list — target 5 NOT FOUND. found flag stays FALSE.

RESULT

Target 5 → NOT FOUND

Comparisons made: 7 · Every element was checked

EXAM POINT — NOT FOUND IS THE WORST CASE

When the target is not in the list, every single element is compared — there is no shortcut.

With 7 elements and target absent, 7 comparisons are always made.

This is the worst case — also happens if the target is the last element.

⚡ Always include the "not found" output in your pseudocode answer. Forgetting to handle the case where the target is absent is a very common exam mistake — it's usually worth at least 1 mark.

Trace Tables

Trace table for linear search

ALGORITHM BEING TRACED

data = [5, 2, 8, 1, 9] target = 8 found = FALSE FOR i = 0 TO 4 IF data[i] == target THEN OUTPUT i found = TRUE END IF NEXT i IF found == FALSE THEN OUTPUT "Not found" END IF

COLOUR KEY · Yellow = changed · Green = output

data=[5,2,8,1,9] · target=8. Finds 8 at i=2 then continues to i=4 (FOR loop doesn't exit early).

TRACE TABLE — BUILDS WITH EACH CLICK

i	data[i]	== target?	found	OUTPUT
0	5	FALSE	FALSE
1	2	FALSE
2	8	TRUE	TRUE	2
3	1	FALSE
4	9	FALSE

Final output: 2 (index where 8 was found). After the loop, found == TRUE so the "Not found" branch does NOT execute. Total comparisons: 5 (the FOR loop runs all 5 iterations from i=0 to i=4).

Trace Tables

Trace table — not found case

SAME ALGORITHM — DIFFERENT TARGET

data = [5, 2, 8, 1, 9] target = 6 ← 6 is NOT in the list found = FALSE FOR i = 0 TO 4 IF data[i] == target THEN OUTPUT i found = TRUE END IF NEXT i IF found == FALSE THEN OUTPUT "Not found" END IF

Target is 6 — not in the list. The loop runs all 5 iterations, found never becomes TRUE, and the final IF outputs "Not found".

TRACE TABLE — NOT FOUND

i	data[i]	== target?	found	OUTPUT
0	5	FALSE	FALSE
1	2	FALSE
2	8	FALSE
3	1	FALSE
4	9	FALSE
Loop ends — found still FALSE → trigger final IF				"Not found"

⚡ Two differences from the found case: (1) found never changes from FALSE — leave the found column blank after the init row. (2) The output "Not found" appears after the loop (in the final IF), not inside it. In your trace table, show this as an extra row after i=4.

Total comparisons: 5. Every element checked. This is the worst case for a 5-element list.

Efficiency

Best, worst and average case

BEST CASE

1

Target is the first element (index 0). Only one comparison is needed. The search finds it immediately and stops (or records found on the first iteration).

AVERAGE

n/2

Target is somewhere in the middle. On average, you'll search through half the list before finding it. For a 100-item list: ~50 comparisons.

WORST CASE

n

Target is the last element OR not in the list. Every single element is compared. For a 100-item list: 100 comparisons needed.

⚡ The spec says "understand the main steps" and "apply to a data set" — you don't need Big O notation. But knowing best=1, worst=n, average=n/2 comparisons is expected and appears in mark schemes.

WORKED EXAMPLES — HOW MANY COMPARISONS?

LIST: [10, 4, 7, 2, 15, 8, 3] · n = 7

Search for 10 → found at i=0 → 1 comparison (best case)

Search for 8 → found at i=5 → 6 comparisons

Search for 3 → found at i=6 → 7 comparisons (worst found)

Search for 5 → not in list → 7 comparisons (worst — not found)

The worst case for a not-found search is the same as finding the last element — both require n comparisons. The exam may ask you to identify which case is being shown.

LINEAR VS BINARY SEARCH — THE KEY DIFFERENCE

Linear search — works on any data, sorted or unsorted. Slower on large lists.

Binary search — requires sorted data. Much faster on large lists. Covered in 2.1.3b.

Identify from Code

Identifying linear search from given code

THREE SIGNATURES OF LINEAR SEARCH

SIGNATURE 1 — A LOOP THROUGH ALL ELEMENTS

A FOR loop from index 0 to the last index (or a WHILE that increments through the list). The loop visits every position.

SIGNATURE 2 — COMPARISON INSIDE THE LOOP

An IF statement inside the loop that compares the current element (data[i]) to the target value.

SIGNATURE 3 — A FOUND FLAG

A boolean variable (usually found) initialised to FALSE before the loop, set to TRUE when the target is located.

See all three in the example opposite. Even if variable names differ, the pattern is the same: loop → compare → flag. That is always a linear search.

EXAM QUESTION STYLE — "NAME THIS ALGORITHM"

nums = [14, 3, 22, 7, 18, 5] search = 7 result = FALSE ← ① found flag FOR k = 0 TO 5 ← ② loop through all IF nums[k] == search THEN ← ③ comparison OUTPUT k result = TRUE END IF NEXT k IF result == FALSE THEN OUTPUT "Not found" END IF

Variables renamed (k instead of i, result instead of found, nums instead of data, search instead of target) — but the three signatures are all there. This is still a linear search.

⚡ "What algorithm is shown?" — the answer is always "linear search" if you see those three signatures together. The specific variable names don't matter. The examiner's mark scheme accepts "linear search" or "sequential search".

Exam Practice

Linear search — applying to data sets

Question 1

A linear search is performed on the list below, looking for the value 14.
List: [8, 3, 14, 22, 5, 14, 9]

(a) How many comparisons are made before the value is first found?
(b) At which index is it first found?

2 marks

Answer

(a) 3 comparisons — checks 8 (no), 3 (no), 14 (yes).
(b) Index 2. Note: the second 14 at index 5 is never reached — the search stops at the first match.

Question 2

Using the same list, a linear search is performed for the value 7.
List: [8, 3, 14, 22, 5, 14, 9]

(a) How many comparisons are made in total?
(b) What is output by the algorithm?

2 marks

Answer

(a) 7 comparisons — every element is checked, none match.
(b) Output: "Not found" (the found flag remains FALSE after the loop, triggering the final IF).

Question 3 — 3 marks

The pseudocode below performs a search on a list. State the name of the algorithm and explain how you identified it. Then state the output when target = 5 and data = [2, 9, 5, 1, 7].

found = FALSE
FOR j = 0 TO 4
  IF list[j] == target THEN
    OUTPUT j
    found = TRUE
  END IF
NEXT j
IF found == FALSE THEN
  OUTPUT "Not found"
END IF

Exam Practice — Answers

Question 3 answered + common mistakes

QUESTION 3 — ANSWER

Algorithm: Linear search (1 mark)

Identified by: loop through every element using a counter (j), comparison of each element to the target inside the loop, and a boolean found flag (1 mark)

Output with target=5, data=[2,9,5,1,7]: checks index 0 (2≠5), index 1 (9≠5), index 2 (5=5 → match) → outputs 2. Loop continues: index 3 (1≠5), index 4 (7≠5). found=TRUE so "Not found" does NOT print. (1 mark)

NOTE ON THE FOR LOOP — WHY INDEX 3 AND 4 ARE STILL CHECKED

With a FOR loop, the loop always runs all iterations — it doesn't exit early when found=TRUE. The output (2) is produced at i=2, then the loop continues to i=3 and i=4. The WHILE version would have stopped at i=2. Both are valid linear searches — the FOR version just continues unnecessarily.

COMMON EXAM MISTAKES — LINEAR SEARCH

1

Saying it only works on sorted data. This is binary search's requirement. Linear search works on any list — sorted, unsorted, even with duplicates.

2

Forgetting the not-found output. Always include the IF found == FALSE check after the loop. Missing this loses a mark.

3

Wrong index for "how many comparisons". If target is at index 3, the answer is 4 comparisons (0,1,2,3 — all inclusive). Students often say 3.

4

Stopping trace too early in FOR loop. A FOR loop always completes all iterations. Only WHILE stops early. In a trace table, show all rows even if found=TRUE partway through.

⚡ Mistakes 1 and 3 are the most common on papers. Linear search ≠ needs sorted data. Comparisons = index of match + 1 (because counting starts at 1, not 0).

Advantages & Disadvantages

Linear search — strengths and weaknesses

✓ ADVANTAGES

No prerequisite — works on unsorted data. No need to sort the list first.

Simple to implement — very short code, easy to understand and trace.

Works with duplicates — finds the first occurrence without issues.

Best case is instant — if the target is first, only 1 comparison needed.

⚡ "Give one advantage of linear search" — always answer: it works on unsorted data / no prerequisite. That's the key distinguishing advantage over binary search.

✗ DISADVANTAGES

Slow on large lists — worst case checks every element. For 1 million items, up to 1 million comparisons.

Inefficient when data is sorted — if the data is already sorted, binary search would be far faster.

Not suitable for very large datasets — databases and search engines use much faster algorithms.

⚡ "Give one disadvantage of linear search" — answer: it is slow / inefficient for large lists because in the worst case every element must be compared. Binary search is much more efficient on sorted data.

Summary

2.1.3a — Linear Search

HOW IT WORKS

Check each element one at a time from index 0. Compare to target. If match: record index, set found=TRUE. If end reached without match: output "Not found". Works on sorted OR unsorted data — no prerequisite.

PSEUDOCODE STRUCTURE

found = FALSE before loop · FOR i = 0 TO LEN-1 · IF data[i] == target THEN set found=TRUE and output i · END IF · NEXT i · After loop: IF found==FALSE THEN output "Not found".

IDENTIFYING FROM CODE

Three signatures: (1) loop through all elements, (2) comparison inside loop to target, (3) found flag. Variable names don't matter — the pattern is what identifies it as linear search.

EFFICIENCY

Best case: 1 comparison (target is first). Average: n/2 comparisons. Worst case: n comparisons (target is last OR not present). Comparisons = target index + 1.

ADVANTAGES vs DISADVANTAGES

Advantage: works on unsorted data, simple to implement. Disadvantage: slow on large lists — checks every element in the worst case. Binary search is faster but requires sorted data. Linear search is the right choice when data is unsorted or the list is small.

2.1.3a Complete

That's Linear Search done!

Next up: 2.1.3b — Binary Search

📝

MARKED WORKSHEET

CSZone.co.uk

🎯

QUIZ

CSZone.co.uk

📊

SLIDES

CSZone.co.uk

Searching AlgorithmsLinear Search

By the end of this video you will be able to...

What is a linear search?

Linear search in pseudocode

Applying it — target found

Applying it — target not found

Trace table for linear search

Trace table — not found case

Best, worst and average case

Identifying linear search from given code

Linear search — applying to data sets

Question 3 answered + common mistakes

Linear search — strengths and weaknesses

2.1.3a — Linear Search

That's Linear Search done!

Searching Algorithms
Linear Search