2.1.3 Searching Algorithms

In this lesson, you will learn how standard searching algorithms are used to find values in lists. You will explore binary search and linear search, apply each algorithm to data sets, compare how they work, and learn to recognise their key features in code or pseudocode.

Standard Searching Algorithms

A searching algorithm is a sequence of instructions used to find a particular item of data in a list, or to confirm that the item is not present. The two searching algorithms you need to know are binary search and linear search. Both can find the same value, but they work in very different ways.

A binary search repeatedly halves the area that still needs to be searched, making it much more efficient for large lists, but it can only be used when the data is already sorted. A linear search examines values one at a time and can be used on sorted or unsorted data.

Binary Search

A binary search repeatedly halves the part of a list that still needs to be searched. A binary search has one essential requirement: the list must already be sorted. This allows the algorithm to determine which half of the list cannot contain the target and discard it.

The algorithm follows these steps:

Find the middle value of the remaining search area.
Compare the target with the middle value.
If they are equal, the target has been found.
If the target is smaller than the middle value, discard the middle value and everything above it, because these values are all too large.
If the target is larger than the middle value, discard the middle value and everything below it, because these values are all too small.
Repeat the process with the remaining half.
If there are no values left to search, the target is not present.

If there are two possible middle values, either can be chosen as long as the same approach is used consistently.

Suppose we want to find the target value 12 in the following sorted list:

[4, 8, 12, 16, 20, 24, 28]

There are seven values, so the middle value is 16. Compare the target with this middle value:

12 < 16

This tells us that the target is smaller than 16. Because the list is sorted into ascending order, every value to the right of 16 is greater than 16, and therefore must also be greater than 12. We can therefore discard 16 and everything above it:

16, 20, 24, 28

The remaining search area is:

[4, 8, 12]

The middle value of the remaining search area is now 8. Compare the target with 8:

12 > 8

This time, the target is larger than the middle value. Because the list is sorted, 8 and every value below it are too small to be the target. We can therefore discard 4 and 8, leaving:

[12]

Only one value remains. Compare it with the target:

12 = 12

The values are equal, so the target has been found.

The search required only three comparisons. This demonstrates the main advantage of binary search: rather than checking one value after another, each unsuccessful comparison removes approximately half of the remaining search area, allowing large lists to be searched much more quickly.

The same steps can also be represented in a high-level programming language. In the Python implementation in Code 1 below, the variables $low$ and $high$ mark the boundaries of the part of the list that is still being searched. The $middle$ position is calculated between these boundaries, and the value at this position is compared with the target.

Codepython

numbers = [4, 8, 12, 16, 20, 24, 28]
target = 12

low = 0
high = len(numbers) - 1
found = False

while low <= high:
    middle = (low + high) // 2

    if numbers[middle] == target:
        found = True
        break
    elif numbers[middle] < target:
        low = middle + 1
    else:
        high = middle - 1

if found:
    print("Target found")
else:
    print("Target not found")

Code 1. Python code implementing binary search by repeatedly checking the middle value and reducing the remaining search area.

Notice how the code follows the same decisions as the worked example. If the middle value is smaller than the target, $low$ moves to the position immediately after the middle, discarding the lower section. If the middle value is larger than the target, $high$ moves to the position immediately before the middle, discarding the upper section.

When recognising binary search from code or pseudocode, look for a middle position being calculated and boundaries being changed so that approximately half of the remaining search area is discarded after each unsuccessful comparison.

Linear Search

A linear search starts at the beginning of a list and checks each item in order until the target value is found or the end of the list is reached.

The algorithm follows these steps:

Start with the first item in the list.
Compare the item with the target value.
If they match, the search is successful.
If they do not match, move to the next item.
Repeat until the target is found or every item has been checked.
If the end of the list is reached without a match, the target is not present.

Unlike binary search, a linear search does not require the list to be sorted.

Suppose we want to find 9 in the following list:

[32, 54, 7, 18, 9, 25]

A linear search begins with the first value and compares each value with the target. If there is no match, it moves to the next value.

First:

32 \neq = 9

The values do not match, so the algorithm moves to the next item.

54 \neq = 9

Again, there is no match, so the search continues.

7 \neq = 9

Then:

18 \neq = 9

Finally:

9 = 9

The values match, so the target has been found and the search can stop.

The target is found after five comparisons, so the algorithm stops immediately without checking the remaining value. If 9 had not appeared in the list, the algorithm would have continued until every value had been checked. This is why linear search can be inefficient for large lists, although unlike binary search it works whether the list is sorted or unsorted.

The same one-by-one process can be seen in the Python implementation in Code 2 below. The variable $index$ identifies the current position in the list, and the loop increases this position as it moves from the beginning towards the end. At each position, the value is compared with the target. As soon as a match is found, the search stops.

Codepython

numbers = [32, 54, 7, 18, 9, 25]
target = 9

found = False

for index in range(len(numbers)):
    if numbers[index] == target:
        found = True
        break

if found:
    print("Target found")
else:
    print("Target not found")

Code 2. Python code implementing linear search by checking each item in sequence until the target is found or the list ends.

Notice that there is no middle position and no attempt to discard part of the list. The algorithm simply checks $numbers[index]$ , moves to the next position, and repeats.

When recognising linear search from code or pseudocode, look for the algorithm moving through the list one item at a time and comparing each item with the target until a match is found or the end of the list is reached.

Comparing Searching Algorithms

Although binary search and linear search can both be used to find a target value, they are suited to different situations. The main difference is that binary search is usually much more efficient, but it can only be used when the data is already sorted. Linear search is more flexible because it works with any list, but it may require many more comparisons.

Table 1. Comparison of binary search and linear search.

Characteristic	Binary Search	Linear Search
Method	Repeatedly halves the remaining search area.	Checks values one at a time from the beginning.
Requires Sorting	Yes	No
Advantage	Very efficient for large sorted lists.	Simple and works with any list.
Limitation	Cannot be used directly on an unsorted list.	May have to check every value.

The choice between the two algorithms therefore depends on the data being searched. If the list is already sorted, binary search is usually the better choice for a large data set. If the data is unsorted, a linear search can be used immediately without first rearranging the values.

GCSE

University Taster