Linear search

Standard searching algorithms: Linear search

2.1.3 Searching and sorting algorithms

Searching and sorting algorithms — Note 2 of 5

Understand the main steps of each algorithm, Understand any pre-requisites of an algorithm, Apply the algorithm to a data set, Identify an algorithm if given the code or pseudocode for it

What you need to know

Linear search is a simple searching algorithm that checks each item in a list one by one, starting from the first item, until the target is found or the end of the list is reached. It works on both sorted and unsorted lists, making it versatile but slower than binary search for large datasets.

What to know

Linear search starts at the FIRST item and checks each item ONE BY ONE, IN ORDER.
It works on any list, whether sorted or unsorted — no pre-requisites needed.
The algorithm stops as soon as the target item is found to avoid unnecessary work.
If the item is not found after checking every element, the search returns False / -1 or 'not found'.
Simple to understand and implement.
Slow for large lists, especially if the item is near the end or not present at all.
Also called sequential search.
A linear search can also be written without a function by using a FOUND FLAG: set found = False before the loop, set it to True when a match is found, then check it after the loop.

Exam technique

Tip:A common exam pattern is to iterate through an array using a for loop with the counter as the array index: theTeam[count].
Tip:When describing a linear search for an item NOT in the list, say it checks all values in order from start to end — don't say 'until found' since it won't be found.
Tip:'Checks each value' is not precise enough — you must state they are checked IN ORDER (sequentially).
Mistake:Putting else: print("Not found") inside the loop prints 'Not found' once for every item that doesn't match. Only decide 'not found' AFTER every item has been checked.

Code examples

Linear search in Python

python

def linear_search(data, target):
    for i in range(len(data)):
        if data[i] == target:
            return i  # Found at index i
    return -1  # Not found

numbers = [15, 7, 3, 5, 13, 8]
print(linear_search(numbers, 13))  # Output: 4
print(linear_search(numbers, 6))   # Output: -1

Linear search with a found flag

python

scores = [12, 7, 5, 10, 3, 2, 7]
target = 7       # the value we are searching for
found = False    # flag: nothing found yet

for i in range(len(scores)):   # check each item IN ORDER
    if scores[i] == target:
        found = True           # set the flag when a match is found

if found:                      # checked AFTER the loop
    print("Found")
else:
    print("Not found")

Ready to test yourself?

Practise 2.1.3 questions

← Previous noteBinary search2.1.3 Searching and sorting algorithms Next note →Bubble sort2.1.3 Searching and sorting algorithms

Back to Searching and sorting algorithms

Revise another OCR GCSE topic: Designing, creating and refining algorithms

def linear_search(data, target): for i in range(len(data)): if data[i] == target: return i # Found at index i return -1 # Not found numbers = [15, 7, 3, 5, 13, 8] print(linear_search(numbers, 13)) # Output: 4 print(linear_search(numbers, 6)) # Output: -1

scores = [12, 7, 5, 10, 3, 2, 7] target = 7 # the value we are searching for found = False # flag: nothing found yet for i in range(len(scores)): # check each item IN ORDER if scores[i] == target: found = True # set the flag when a match is found if found: # checked AFTER the loop print("Found") else: print("Not found")