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]: