A linear search (also called a sequential search) checks each element of a list one by one, from the beginning, until the target item is found or the entire list has been checked. It is the simplest search algorithm.
Key property: The list does NOT need to be sorted. This is the main advantage over binary search.
How Linear Search Works
Given a list: [4, 9, 2, 15, 7, 3, 11, 6] — searching for 7:
4 ✗
9 ✗
2 ✗
15 ✗
7 ✓
3
11
6
Checked indices 0–4 (5 comparisons). Found at index 4.
Pseudocode
// Linear search — returns index of target, or -1 if not foundFUNCTION linearSearch(list, target)
FOR i = 0 TO length(list) - 1
IF list[i] == target THENRETURN i // Target found at index iEND IFEND FORRETURN -1 // Target not foundEND FUNCTION
Worked Example — Trace Table
List: [12, 5, 8, 3, 19, 7] — Search for 19
Step-by-step trace:
Pass
i
list[i]
list[i] == 19?
Action
1
0
12
No
Continue
2
1
5
No
Continue
3
2
8
No
Continue
4
3
3
No
Continue
5
4
19
Yes
Return 4 (found)
Result: Target 19 found at index 4. Took 5 comparisons.
What If the Item Is Not Found?
The algorithm checks every element. If none match, it returns -1 (or "not found") after checking the entire list.
Worst case: The target is the last element, or it isn't in the list at all — n comparisons (where n = number of elements).
Linear Search — Advantages and Disadvantages
Advantages
Disadvantages
Works on unsorted lists
Slow for large lists — checks every element in worst case
Simple to understand and implement
Less efficient than binary search for sorted data
Works on any data type
Time complexity O(n) — linear
No preprocessing (sorting) needed
Not suitable for very large datasets
When to Use Linear Search
When the list is unsorted or cannot be sorted
When the list is small (the overhead of sorting isn't worth it)
When you only need to search once (sorting first would be wasteful)
When searching for the first occurrence of a value in a stream
Exam tip: In an exam trace table for linear search, work through each element in order and show the comparison made each time. The key advantage is it works on unsorted data. The key disadvantage is it is O(n) — slow for large lists. Always state the number of comparisons made. If the target is not found, state "not found" or "returns -1".
⚠️ Common Mistakes
Saying linear search requires a sorted list — it does NOT (that's binary search)
Stopping the trace too early — always show all comparisons until found or end of list
Confusing index positions — lists in OCR start at index 0
Saying it "always" checks every element — it stops as soon as the target is found
Not returning -1 (or equivalent) when the item is not found
✅ Notes completed!
▶
Video coming soon
Click slide or press arrow keys to navigate
Worksheet — 2.1.2a Linear Search
8 questions · 17 marks
Q1Describe how a linear search works.[2]
✅ Mark scheme
A linear search checks each element of a list one at a time [1], starting from the beginning (index 0), until the target item is found or the entire list has been checked [1].
Q2State one advantage and one disadvantage of using a linear search.[2]
✅ Mark scheme
Advantage: works on unsorted lists [1]; disadvantage: slow for large lists — must check every element in worst case [1].
Q3A linear search is performed on the list: [6, 14, 3, 9, 21, 5]. How many comparisons are needed to find the value 21? Show your working.[3]
✅ Mark scheme
Compare 6 — no [1]; compare 14 — no; compare 3 — no; compare 9 — no; compare 21 — YES [1]; 5 comparisons needed [1]. 21 is at index 4.
Q4What is returned by a linear search algorithm if the target value is NOT in the list?[1]
✅ Mark scheme
-1 (or an equivalent value indicating "not found") [1].
Q5Does a linear search require the list to be sorted? Explain your answer.[2]
✅ Mark scheme
No [1] — a linear search checks each element one by one regardless of order. It does not rely on the list being sorted to work correctly. This is its main advantage over binary search [1].
Q6Complete the trace table for a linear search on the list [8, 3, 17, 5, 11] searching for target = 5.[4]
✅ Mark scheme
i=0: list[0]=8, 8==5? No, continue [1]; i=1: list[1]=3, 3==5? No, continue [1]; i=2: list[2]=17, 17==5? No, continue [1]; i=3: list[3]=5, 5==5? YES — return index 3 [1]. Total: 4 comparisons.
Q7Give two situations where a linear search would be preferred over a binary search.[2]
✅ Mark scheme
Any two: when the list is unsorted and cannot be sorted [1]; when the list is small [1]; when the search only needs to be done once (sorting first would be more expensive) [1].
Q8What is the worst-case number of comparisons for a linear search of a list containing n items?[1]
✅ Mark scheme
n comparisons [1] — when the target is the last element, or not in the list at all.
?
out of 17 — self-mark above
Topic Quiz
Question 1 of 15
You scored
out of 15
Card 1 of 8
Click to reveal definition
🎉
Complete!
Term
Definition
🎯
Mini Test — 2.1.2a Linear Search
10 questions · 10 marks · 10 minutes
⏱ 10:00
10 marks
Section A — Multiple Choice [5 marks]
Q1What is the main advantage of linear search over binary search?
Q2A linear search on [3, 7, 1, 9, 5] is looking for 9. How many comparisons are made?
Q3What does a linear search return if the target is not found in the list?
Q4What is the worst-case number of comparisons for a linear search on a list of 20 items?
Q5When would you choose a linear search over a binary search?
Section B — Short Answer [5 marks]
Q6Describe how a linear search finds a target value in a list.
Mark schemeStarting at index 0, compare each element with the target in order. If a match is found, return the index. If the end of the list is reached without a match, return -1. [1]
Q7State one advantage of linear search.
Mark schemeWorks on unsorted lists; simple to implement; works on any data type; no preprocessing needed. [1 for any valid advantage]
Q8A list contains 1000 items. In the worst case, how many comparisons does a linear search make? Explain why.
Mark scheme1000 comparisons [1] — in the worst case, the target is the last item in the list (or not present at all), requiring every element to be checked. [1 for explanation]
Q9For list [20, 15, 3, 8, 12], trace through a linear search for target = 3. State how many comparisons.
Mark schemei=0: 20≠3; i=1: 15≠3; i=2: 3=3 — found at index 2 [1]; 3 comparisons made [1]. [1 for correct count, 1 for correct index]
Q10Does linear search require the list to be sorted? Yes or no, and why.
Mark schemeNo — linear search checks each element one by one regardless of order, so it works correctly on both sorted and unsorted lists. [1]