Skip to content
VirtusAcademy

Linear Search

FoundationHigherAQA

Practise Linear Search for GCSE Computer Science with this free worksheet and full mark scheme — Foundation and Higher exam-style questions with worked answers for AQA GCSE Computer Science (8525). A linear search checks each item in turn until it finds the target or reaches the end of the list.

Free downloads

These worksheets and mark schemes are original, written for Virtus Academy and checked against the current AQA specification. Every worksheet comes with a full mark scheme.

Foundation

WorksheetFoundation · PDFMark SchemeFoundation · PDF

Higher

WorksheetHigher · PDFMark SchemeHigher · PDF

Topic overview

A linear search checks each item in a list one at a time, from the start, until the target is found or the end is reached.

Its great advantage is that it works on any list, whether sorted or not. This is the key difference from a binary search and the point most often examined.

The disadvantage is speed. For a list of n items, the worst case requires n comparisons, because the target may be the last item or absent altogether. On average it takes about n divided by 2 comparisons. For a list of 1000 items that is up to 1000 checks, whereas a binary search on the same sorted list would need at most 10.

Revision notes

How it works

Start at the first item. Compare it with the target.

If it matches, stop and report the position. If not, move to the next item and repeat. If the end of the list is reached without a match, report that the item is not present.

The key advantage

It works on unsorted lists.

This is the crucial difference from a binary search, which requires the list to be sorted first. If the list is unsorted and will only be searched once, a linear search is often the better choice overall.

Efficiency

Worst case: n comparisons for a list of n items, when the target is last or absent.

Best case: 1 comparison, when the target is first. Average: about n divided by 2. For 1000 items that is up to 1000 checks, against at most 10 for a binary search.

Key points

  • A linear search checks items one at a time.
  • It starts at the first item.
  • It works on unsorted lists.
  • The worst case is n comparisons.
  • The best case is 1 comparison.
  • It is slower than a binary search on large lists.

Worked examples

Example 1

State the main advantage of a linear search over a binary search. [1 mark]

Working

It works on an unsorted list, whereas a binary search requires the list to be sortedstate the advantage

Example 2

A list contains 60 items. State the maximum number of comparisons a linear search needs. [2 marks]

Working

The worst case is when the target is the last item or is not present at allidentify the worst case
so the maximum is 60 comparisonsstate the number

Example 3

Explain why a linear search may be preferred for a small unsorted list searched only once. [2 marks]

Working

A binary search would require the list to be sorted first, which takes timestate the alternative's cost
so for a single search of a small list, sorting then searching is slower than simply checking each itemexplain the comparison

Common mistakes

  • Saying a linear search needs a sorted list.

    It works on any list — that is its main advantage.

  • Giving the worst case as n divided by 2.

    That is the average; the worst case is n.

  • Forgetting the item may be absent.

    The worst case includes searching the whole list and finding nothing.

  • Saying it is always slower than a binary search.

    For a small unsorted list searched once, it can be faster overall.

Exam tips

  • Name working on unsorted lists as the key advantage.
  • Distinguish worst case from average case.
  • Remember the worst case includes the item being absent.
  • Compare fairly by including the cost of sorting.

Key terms

Linear search
Checking each item in turn from the start.
Worst case
The maximum number of comparisons needed.
Unsorted
Not arranged in order, which a linear search allows.
Comparison
One check of an item against the target.

Related topics

Written and reviewed against the current AQA specification. Spotted an error? Let us know.