Linear Search Algorithm

This lesson covers the linear search algorithm as required by OCR J277 Section 2.2. Linear search is one of the standard searching algorithms you must know for the OCR GCSE Computer Science exam, and you need to be able to describe how it works, write it in pseudocode or a programming language, and trace through it using a trace table.

---

What Is Linear Search?

Linear search (also called sequential search) is the simplest searching algorithm. It works by checking each item in a list, one at a time, from the first element to the last, until the target item is found or the end of the list is reached.

Think of it like looking for a specific book on a shelf by checking every book from left to right, one by one.

---

How Linear Search Works

1. Start at the first element of the list (index 0).
2. Compare the current element with the target value.
3. If the current element matches the target, return its position — the search is complete.
4. If it does not match, move to the next element.
5. Repeat steps 2–4 until the target is found or the end of the list is reached.
6. If the end of the list is reached without finding the target, report that the item is not found.

---

Linear Search in OCR Pseudocode

function linearSearch(list, target)
    for i = 0 to list.length - 1
        if list[i] == target then
            return i
        endif
    next i
    return -1
endfunction

A return value of -1 indicates the item was not found.

Linear Search in Python

def linear_search(lst, target):
    for i in range(len(lst)):
        if lst[i] == target:
            return i
    return -1

# Example usage
numbers = [5, 3, 8, 1, 9, 2, 7]
result = linear_search(numbers, 9)
if result != -1:
    print("Found at index", result)
else:
    print("Not found")

OCR Exam Tip: When writing search algorithms in pseudocode, always use the OCR convention of for i = 0 to n ... next i for loops. The examiner wants to see you follow the OCR pseudocode reference language.

---

Tracing Through Linear Search

Let us trace through searching for the value 7 in the list [4, 2, 7, 1, 9]:

Step	Index (i)	list[i]	Match?	Action
1	0	4	No	Move to next
2	1	2	No	Move to next
3	2	7	Yes	Return 2

The value 7 was found at index 2 after 3 comparisons.

---

Properties of Linear Search

Property	Detail
Data requirement	Works on both sorted and unsorted data
Best case	Target is the first element — 1 comparison (O(1))
Worst case	Target is the last element or not present — n comparisons (O(n))
Average case	Approximately n/2 comparisons
Simplicity	Very easy to understand and implement

---

When to Use Linear Search

Linear search is a good choice when:

• The data is unsorted and cannot easily be sorted.
• The list is small (e.g. fewer than 100 items).
• You need a simple algorithm that is easy to implement.
• The data structure does not support random access.

Linear search is a poor choice when:

• The list is very large — it becomes slow because every item may need to be checked.
• The data is already sorted — binary search would be much faster.

---

Worked Exam-Style Example

Question: The array names contains: ["Ali", "Ben", "Cat", "Dan", "Eve"]. Write an algorithm in pseudocode to search for a name entered by the user using linear search.

Answer:

names = ["Ali", "Ben", "Cat", "Dan", "Eve"]
target = input("Enter name to search for: ")
found = false

for i = 0 to names.length - 1
    if names[i] == target then
        print("Found at position " + str(i))
        found = true
    endif
next i

if found == false then
    print("Name not found")
endif

---

Summary

• Linear search checks each element one by one from the start.
• It works on sorted and unsorted data.
• The worst case is O(n) — checking every element.
• It is simple but inefficient for large datasets.
• You must be able to write it in pseudocode, trace through it, and explain when it is appropriate.

OCR Exam Tip: A common 2-mark question is: "Describe how a linear search works." Always say: (1) start at the first item and compare it to the target, and (2) if it does not match, move to the next item, repeating until found or the end is reached.

---

Extended Trace: Searching for a Value That Is Not Present

Now let us trace a worst-case example. Search the list [4, 2, 7, 1, 9] for the value 6 (which is not in the list):

Step	Index (i)	list[i]	Match?	Action
1	0	4	No	Move to next
2	1	2	No	Move to next
3	2	7	No	Move to next
4	3	1	No	Move to next
5	4	9	No	End of list — return -1

Every single element was compared — this is the worst case. Notice the loop terminates naturally when i reaches list.length, and the function returns the "not found" indicator (-1).

---

Full Trace Table Including All Variables

A more formal trace table for linear search on [4, 2, 7, 1, 9] looking for 7: