Preview

The whole resource, exactly as a class sees it. Answers and marking are held back.

Linear and binary searching

A search algorithm tries to locate a target value. Linear search checks values in order from the beginning and can work with unsorted data. Binary search repeatedly checks the middle of the remaining data and requires that data to already be sorted. OCR requires the steps, prerequisites, application and recognition of both algorithms; you do not need to memorise a complete implementation.

Multiple choice1 mark

What must be true before binary search can be used correctly?

AThe data must contain only strings
BThe data must already be sorted
CThe target must be the middle item
DThere must be exactly ten items

Two search strategies

Linear search checks items one at a time from the start until the target is found or there are no items left. It works on unsorted data.

Binary search checks the middle item of sorted data. If that is not the target, it discards the half that cannot contain the target and repeats on the remaining half. Each comparison can remove roughly half the remaining search area.

The faded values are no longer possible candidates. Binary search does not revisit them.

The runnable example below implements linear search and returns an index, or -1 when the target is absent. Before running it, predict both results and count how many array elements are examined in each call.

Worked example

def linear_search(values, target):
    position = -1
    index = 0
    while index < len(values) and position == -1:
        if values[index] == target:
            position = index
        index = index + 1
    return position

print(linear_search([17, 4, 23, 9], 23))
print(linear_search([17, 4, 23, 9], 8))

Multiple choice1 mark

A linear search looks for 23 in [17, 4, 23, 9]. How many item comparisons are made?

Supported practice: complete a linear search

The loop already visits every value and found is correctly initialised to False. Replace pass with a decision that changes found to True when the current value equals target.

The checks will test one target that is present and one that is absent. Do not set found to False inside an else, because a later non-match could erase an earlier successful match.

Coding task3 marks

# Complete the linear search so found becomes True when target is present.
values = [12, 7, 19, 4, 15]
target = 19
found = False
for value in values:
    pass

Applying binary search

For [3, 8, 12, 17, 24, 31, 46] and target 31, check the middle value 17. Because 31 is greater, discard 3, 8, 12, 17. Check the middle of the remaining section and continue until 31 is found.

Each middle comparison has three possible outcomes:

the middle value equals the target: the target is found and the search stops;
the target is smaller: continue with the lower half;
the target is larger: continue with the upper half.

Do not say binary search “checks every other item”. Its defining action is repeatedly selecting the middle of the remaining ordered search area.

Written answer4 marks

Apply binary search to find 42 in [4, 9, 15, 23, 31, 42, 58]. State each value compared with 42 and what is discarded after each unsuccessful comparison.

Begin with the middle value. After each unsuccessful comparison, state which part of the sorted search area can be discarded.

Students type their answer here.

Multiple choice1 mark

Which description identifies binary search in a code listing?

AIt always starts at index zero and increases by one
BIt swaps adjacent values
CIt splits data and merges sorted sublists
DIt compares a middle item and changes upper or lower search bounds

Written answer3 marks

A game stores the latest ten player names in the order they joined. Recommend linear or binary search for finding a name, and justify your answer.

Use the fact that the names are not stated to be sorted. You may discuss the alternative if the data could be sorted first.

Students type their answer here.

Written answer3 marks

Explain why binary search usually needs fewer comparisons than linear search on a large sorted list.

Compare how much of the remaining data each unsuccessful comparison removes.

Students type their answer here.

Review

Linear search works from the first value through the data in order and does not require sorted data. If the target is absent, it reaches the end without finding a match. Binary search requires sorted data, compares a middle value and either stops on equality or restricts the search to the only half that can still contain the target. In an exam, show each comparison and each change to the remaining search area.