Community resourceWorksheet

OCR H446 2.3.1 Linear and binary search

Part 5 of 16 · H446 2.3.1 · Algorithms

Binary search is examined in H446 2.3.1 alongside linear search, and the mark is usually lost on the precondition or on bounds that drift during a trace. This worksheet has students search by hand, trace the shrinking bounds, write both algorithms in Python and then pick the right one for a stated situation.

Students will:

  • state the precondition that makes discarding half a list safe
  • trace low, high and middle values while a search narrows towards a target
  • record every compared value when searching the same data both ways
  • implement linear and binary search that return an index or minus one
  • recommend a search for a short one-off list and for a large maintained catalogue

Inside: 5 explanation cells, 1 multiple-choice question, 1 fill-in-the-blanks cell, 2 written answers, 1 Python task and 1 trace table. 25 marks, about 25 to 40 minutes.

Series: H446 2.3.1 · Algorithms, part 5 of 16.

Shared by Coding PathwayVerified teacher

  • 11 cells
  • About 30 minutes
  • CC BY-SA 4.0
  • Shared 31 Aug 2026
  • Updated 3 Sept 2026

Preview

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

Linear and binary search

Search must return a result and preserve its preconditions. Binary search requires sorted/ordered data; 'organised' is not precise enough.

By the end, you will be able to

  • perform both searches manually;
  • explain binary narrowing and boundaries;
  • read, trace and write both algorithms;
  • select a search for a scenario.

Reactivate: integer division chooses a middle index.

Worked model: two search strategies

Linear and binary search strategies37121824314257linear: test each value until found or exhaustedbinary: on sorted data, compare with middle and discard one half

Searching for 31 linearly may test 3, 7, 12, 18, 24, 31. Binary search compares 18, discards the lower half, then compares 31. Bounds must move beyond middle: low = middle + 1 or high = middle - 1.

Multiple choice1 mark

What precondition permits binary search to discard half safely?

  • AThe values are sorted by the searched key
  • BThe values are unique
  • CThe list has even length
  • DThe target is present
Trace table5 marks

Trace the boundaries while searching for 24.

Enter a value only when it changes. Record output in order.

Use one row for each pass through the loop. Fill in a box only when that value changes on that row, and leave the rest blank.

ProgramPython
  1. data = [3,7,12,18,24,31,42,57]
  2. target = 24
  3. low = 0
  4. high = len(data)-1
  5. found = False
  6. while low <= high and found == False:
  7. middle = (low+high)//2
  8. if data[middle] == target:
  9. found = True
  10. print(middle)
  11. elif data[middle] < target:
  12. low = middle+1
  13. else:
  14. high = middle-1
Trace table with 10 columns
Rowdatatargetlowhighfoundmiddlelow <= high and found == Falsedata[middle] == targetdata[middle] < targetOutput
1
2
3
4
5
6
7
Written answer5 marks

Manually search the displayed data for 42 using both algorithms. Record every compared value and explain why each binary discard is valid.

List comparisons in order.

Students type their answer here.

Independent transfer: write both searches

Return the index of target or -1. binary_search may assume ascending sorted data.

Coding task10 marks
def linear_search(data, target):
    pass

def binary_search(data, target):
    pass
Written answer5 marks

A 30-item list is searched once and arrives unsorted; a 100,000-item catalogue is maintained sorted and searched repeatedly. Recommend a search for each.

Include preprocessing and growth.

Students type their answer here.

Closed-book checkpoint

Complete each sentence from memory. There is no answer bank and correctness is held for teacher review.

Fill in the blanks4 marks
Binary search requires data to be completion 1 by the searched key. It compares the target with the completion 2 item. If that item is too small, move completion 3 beyond it; if too large, move completion 4 before it.

Review your understanding

Before submitting, check that you can explain the central distinction in your own words, expose the intermediate state that supports your answer and apply the method in an unfamiliar context.