Searching Algorithms: AQA GCSE Computer Science Revision

If you are preparing for your exams, this gcse computer science revision guide will help you secure top marks. Whether you are studying AQA or preparing for OCR GCSE computer science, mastering how to find data is a core requirement.

What is a search algorithm in computer science?

Computing algorithms are the foundation of all software. Simply put, an algorithm is a sequence of logical instructions for carrying out a task. A search algorithm is a standard step-by-step procedure used to locate specific data among a collection of records.

When you write a program or engage in coding, you need these standard methods to solve problems. Whether you are searching for a contact on your phone or a particular record in a database, you are using a search algorithm.

Why are searching algorithms important in computer science?

In the modern world, massive amounts of data are constantly being generated. A computer system must be able to retrieve that data accurately. In computer programming, we use these sets of instructions to ensure that applications run smoothly.

If a database takes too long to compute a query and find a record, the entire program becomes unusable. Understanding how to locate a key number or string quickly is a foundational skill for any programmer.

What are the different types of searching algorithms?

Today, you will learn about searching algorithms in detail. While there are many complex methods used in advanced computing, the syllabus focuses on the two most common types you need to know: the linear search and the binary search. Both of these common algorithms have specific use cases depending on how the data is structured.

How do linear and binary search algorithms work?

To understand how these methods operate, we must look at the specific instructions they follow. Here is a breakdown of how both linear and binary search algorithms work.

1. The Linear Search

This is the brute-force method. A linear search (sometimes hastily mistyped as an inear search in exams!) is a simple process that checks each item in the list starting from index 0. Because the base logic is so simple, it is highly reliable.

Diagram showing a Linear Search algorithm finding the number 23 in a list. Arrows point to each number in sequence (2, 5, 8, 12, 16) checking them one by one until the target (23) is found at index 5. — A visual demonstration of Linear Search checking items one by one to find the value 23. This illustrates the ‘brute force’ method.

How it works:

Start at the very beginning of the list (index 0).
Compare the current item with the value to be found.
Check whether they are the exact same value.
If a match is made, output the index position and stop the search.
Otherwise, move to the next item in the list.
Repeat this instruction step until you reach the end.
If you check every single value and do not find the target, the program returns false.

Here is how you might write a simple linear search using pseudocode:


FOR i = 0 TO list.length - 1
    IF list[i] == target THEN
        PRINT "Item found"
        RETURN True
    END IF
NEXT i
RETURN False

2. The Binary Search

A binary search is an alternative divide and conquer algorithm. It is much more efficient, but requires the data list to be sorted first. To perform binary searching algorithms, the computer repeatedly splits the search space in half.

A step-by-step visual diagram of a binary search algorithm finding the number 23 in a sorted list. It shows four stages: calculating the initial midpoint (16), discarding the left half, calculating the new midpoint (56), discarding the right half, and finally locating the target value (23) at index 5. — Visual trace of a binary search algorithm locating the value 23 in a sorted array. This example demonstrates the ‘divide and conquer’ method required for AQA GCSE Computer Science.

How it works:

Find the middle item of the list (the mid position).
Check the value at the midpoint against the value to be found.
If they match, you stop!
If the midpoint is greater than the target value, you know the item must be in the lower half of the list. You discard the right half entirely.
If the midpoint is less than the target value, the item must be in the upper half of the list. You discard the left half.
Repeat this process on the remaining half until the item is found.

When calculating the mid position, if you get a decimal, you usually round down to the nearest whole number using integer division (DIV).

What are the advantages and disadvantages of different searching algorithms?

When comparing linear and binary methods, students must evaluate their trade-offs. The main advantage of a linear search is that it works on unsorted data. Its main disadvantage is that it is incredibly slow for large datasets.

Conversely, the advantage of a binary search is its incredible speed, but its disadvantage is the strict requirement that the list must be ordered beforehand.

How do you calculate the time complexity of a search algorithm?

In GCSE computer science, time complexity refers to how the time taken to run an algorithm grows as the size of the data increases. For a linear search, the time complexity is proportional to the number of items (O(N)); if you have 100 items, it might take 100 checks.

For a binary search, the time complexity is logarithmic (O(log N)). Because the list halves every step, even an array of one million items only takes about 20 checks to find the target value!

What are some real-world applications of search algorithms?

To help revise these concepts, let’s look at real-world applications of search algorithms:

The Messy Drawer (Linear Search): Looking for a specific pair of keys in a messy drawer. You check the first item, then the next. It is slow, but works perfectly on unsorted objects.
The Dictionary (Binary Search): Finding a word in a dictionary. You open the book to the middle, check if your word comes before or after that page, and ignore the other half. It is fast, but only works because the dictionary is alphabetically sorted.

How can search algorithms be optimized?

Search algorithms can be optimized by organizing the data first. If you are dealing with a massive database, applying a standard sorting algorithm beforehand will enable you to use a binary search instead of a linear one. In real-world software engineering, developers also use data structures like Hash Tables or search indexes to further optimize retrieval speeds.

What is the difference between searching and sorting algorithms?

A common question is the difference between searching and sorting. A searching algorithm is used to find a specific item within a dataset. A sorting algorithm is used to arrange a dataset into a specific order (such as numerical or alphabetical). Searching and sorting are deeply connected because sorting algorithms enable more efficient binary searches to function.

Trace Table Builder: Dry Run Practice

In your exam, you will likely be asked to trace a searching algorithm using a table or a flowchart. Let’s trace a binary search finding the number 23.

Our List: [2, 5, 8, 12, 16, 23, 38, 56, 72, 91] (Start: 0, End: 9)

Pass 1:

Mid = (0 + 9) DIV 2 = 4.
The value at index 4 is 16.
16 is smaller than 23, so 23 must be in the upper half. We discard the lower half.
New Start = mid + 1 (Start is now 5).

Pass 2:

Mid = (5 + 9) DIV 2 = 7.
The value at index 7 is 56.
56 is greater than 23, so we discard the right half.
New End = mid – 1 (End is now 6).

Pass 3:

Mid = (5 + 6) DIV 2 = 5.
The value at index 5 is 23.
The value matches! The search returns index 5 and stops.

Ready To Master The Full Topic?

You’ve explored the theory behind linear and binary search. Now, dive deeper into our complete AQA course. Whether you want to practice your sorting algorithms or learn how to write a Python program, our resources will prepare you for your final exam.