Community resourceWorksheet

1CP2-CT-8.4 Binary search halving sorted data

Part 4 of 5 · 1CP2-CT-8 · Tracing, debugging, sorting and searching

Binary search finds an item in sorted data. It compares the target with the middle item. If they are unequal, it discards the half that cannot contain the target. This repeated halving is a divide-and-conquer method.

Students will:

  • apply binary search only to sorted data
  • update lower and upper bounds after each comparison
  • trace a complete search systematically
  • repair a boundary update that fails to shrink the range

Inside: 6 explanation cells, 1 fill-in-the-blanks cell, 3 multiple-choice questions, 4 written answers and 1 trace table. 16 marks, about 45 minutes.

Series: 1CP2-CT-8 · Tracing, debugging, sorting and searching, part 4 of 5.

Shared by Coding PathwayVerified teacher

  • 15 cells
  • About 45 minutes
  • CC BY-SA 4.0
  • Shared 17 Aug 2026

Preview

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

Binary search: halving sorted data

Binary search finds an item in sorted data. It compares the target with the middle item. If they are unequal, it discards the half that cannot contain the target. This repeated halving is a divide-and-conquer method.

1. Keep a searchable range

Binary search halves a sorted listtarget = 3149152231384431 > 22discard 4, 9, 15 and 22313844found

Store lower and upper boundaries. Calculate the middle position using integer division. If the target is greater than the middle value, move the lower boundary above the middle. If it is smaller, move the upper boundary below the middle.

Fill in the blanks3 marks
Binary search requires gap 1 data. It first checks the gap 2 item and then discards about gap 3 of the remaining search range.
  • half
  • middle
  • random
  • sorted
Multiple choice1 mark

Why is binary search unsuitable for [18, 4, 27, 9, 12] as shown?

  • AIt contains numbers
  • BIt is not sorted
  • CIt has five items
  • DThe target is unknown

2. Apply boundary updates

Search for 42 in [5, 11, 18, 24, 31, 42, 57]. The middle is 24. Since 42 is greater, keep [31, 42, 57]. Its middle is 42, so the target is found after two comparisons. The discarded lower items remain real data; they are simply outside the current search range.

Written answer3 marks

Apply binary search to find 8 in [2, 5, 8, 12, 17, 21, 30]. State the values compared, in order.

Use the middle of each remaining range.

Students type their answer here.

Written answer2 marks

Search for 14 in [3, 7, 10, 14, 18, 22, 29]. State the first comparison and the next range retained.

Show why one half is discarded.

Students type their answer here.

3. Trace the implementation

Read this code without running it.

values = [3, 8, 12, 17, 25]
target = 17
low = 0
high = len(values) - 1
found = False
while low <= high and found == False:
    middle = (low + high) // 2
    if values[middle] == target:
        found = True
    elif values[middle] < target:
        low = middle + 1
    else:
        high = middle - 1
print(found)
Multiple choice1 mark

What exact value is printed?

  • A0
  • B1
  • CFalse
  • DTrue
Written answer3 marks

Explain the two comparisons that lead to the output.

Name each compared value and boundary change.

Students type their answer here.

Trace table4 marks

Complete the binary-search trace.

Record low, high, middle and found for each loop iteration.

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. values = [2, 6, 9, 13, 18, 24, 31]
  2. target = 24
  3. low = 0
  4. high = len(values) - 1
  5. found = False
  6. while low <= high and found == False:
  7. middle = (low + high) // 2
  8. if values[middle] == target:
  9. found = True
  10. elif values[middle] < target:
  11. low = middle + 1
  12. else:
  13. high = middle - 1
  14. print(found)
Trace table with 10 columns
Rowvaluestargetlowhighfoundmiddlelow <= high and found == Falsevalues[middle] == targetvalues[middle] < targetOutput
1
2
3
4
5
6

4. Avoid a non-shrinking range

When the middle value is too small, use low = middle + 1. Using low = middle can leave the same middle inside the range, so a search may repeat without progress. The matching upper update is high = middle - 1.

Written answer2 marks

A search uses low = middle when the middle value is too small. State the correction and explain why it matters.

Connect the +1 to progress and termination.

Students type their answer here.

Multiple choice1 mark

Which description correctly distinguishes binary search from merge sort?

  • ABoth are searches
  • BBinary search halves a sorted search range; merge sort divides data to sort it
  • CMerge sort requires a target
  • DBinary search joins two sorted lists

Route forward

You can apply, trace and amend binary search. The checkpoint will mix formal tracing, error repair, bubble sort and binary search without first-teaching new methods.