python-programming / searching-and-sorting · Lesson 23

Lesson 23 — Searching and sorting

Binary Search

Search sorted data by repeatedly discarding half of the remaining values.

Binary search only works when the data is already sorted. It checks the middle item, then continues in either the lower half or the upper half.

Predict

Read the code first. Do not run it yet.

binary-search-predict.py

numbers = [3, 8, 12, 17, 25, 31, 44]
target = 25
low = 0
high = len(numbers) - 1
mid = (low + high) // 2
print(mid, numbers[mid])

Predict before running

What index is stored in mid?
What value is checked first?
Should the next search continue left or right of the middle?

Investigate

Use this code to explain exactly how the program works.

binary-search-investigate.py

numbers = [3, 8, 12, 17, 25, 31, 44]
target = 31
low = 0
high = len(numbers) - 1
found = False
while low <= high and found == False:
    mid = (low + high) // 2
    if numbers[mid] == target:
        found = True
    elif target < numbers[mid]:
        high = mid - 1
    else:
        low = mid + 1
print(found)

Investigate the code

Trace low, high and mid after each comparison.
Why is // used to calculate the middle index?
What prerequisite must be true before binary search is used?

The binary-search process

How it works

Start with the lowest and highest valid indices.
Check the item in the middle.
If it matches, the search ends.
If the target is smaller, discard the upper half. If it is larger, discard the lower half.
Repeat until the item is found or no search area remains.

binary_search.py

numbers = [3, 8, 12, 17, 25, 31, 44]
target = 17
low = 0
high = len(numbers) - 1
found = False

while low <= high and found == False:
    mid = (low + high) // 2
    if numbers[mid] == target:
        found = True
    elif target < numbers[mid]:
        high = mid - 1
    else:
        low = mid + 1

print(found)

Output

True

Sorted data requiredBinary search is not valid on an unsorted list.

Understand the stepsFocus on being able to trace, apply and recognise the algorithm. Different correct implementations can look slightly different.

Recognise and apply the algorithmBe able to follow these characteristic steps on a data set and recognise the algorithm from program code. Correct implementations can use different variable names or loop structures, so focus on the behaviour rather than memorising one exact version.

Self-study guide

Binary search repeatedly checks the middle item of a sorted data set and discards half of the remaining search area. Its essential prerequisite is that the data is already sorted in the same order used by the comparisons.

Like linear search, OCR expects understanding and application rather than memorisation of a particular code listing. Focus on the boundaries, the middle item and which half can be discarded.

OCR focusUnderstand, apply and identify binary search. Always state the sorted-data prerequisite when it is relevant.

OCR Exam Reference Language ↔ Python

OCR Exam Reference Language / term	Python	What to remember
`Binary search`	`low/high/middle loop in Python`	Repeatedly inspect the middle item.
`prerequisite: sorted data`	`sorted Python list`	Binary search is not valid on arbitrary unsorted data.
`discard half`	update `low` or `high`	Comparison decides which half cannot contain the target.

Read both formsIn an examination you may see OCR Exam Reference Language even when you have learned the idea in Python. Translate the structure, not just the symbols.

Worked example

The boundaries describe the part of the array that could still contain the target.

lesson-23-worked.py

values = [3, 7, 12, 18, 25, 31, 44]
target = 25

low = 0
high = len(values) - 1
position = -1

while low <= high and position == -1:
    middle = (low + high) // 2

    if values[middle] == target:
        position = middle
    elif values[middle] < target:
        low = middle + 1
    else:
        high = middle - 1

print(position)

Output

Work through it line by line

Initially the possible search area is the whole sorted list.
The first middle index is 3, containing 18.
18 is smaller than 25, so indexes 0–3 can be discarded.
The new middle is index 5, containing 31, so the upper part is discarded.
Index 4 contains 25, so the search succeeds.

Another example

An absent target eventually makes the search area empty.

lesson-23-example-2.py

values = [2, 6, 9, 14, 20]
target = 13

low = 0
high = len(values) - 1
position = -1

while low <= high and position == -1:
    middle = (low + high) // 2
    print(values[middle])

    if values[middle] == target:
        position = middle
    elif values[middle] < target:
        low = middle + 1
    else:
        high = middle - 1

Output

9
14

Why this example matters

The first middle value is too small, so the lower half is discarded.
The next middle value is too large, so the remaining upper item is discarded.
The boundaries then cross, meaning the target is absent.

Common mistakes

Avoid these errors

Using binary search on unsorted data.
Updating low when the middle value is too large, or high when it is too small.
Forgetting that middle is an index, not the data value itself.

Exam-safe warningThe sorted-data prerequisite is fundamental. If the data is not sorted, binary search cannot safely discard half the values.

Exam-ready checklist

You should now be able to

State the sorted-data prerequisite.
Apply binary search manually.
Track low, high and middle positions.
Identify binary search from code/ERL.
Explain why each comparison permits half the search area to be discarded.

What you have learned

Binary search requires sorted data.
It checks the middle item and discards half of the remaining search area.
It repeats until the target is found or the search area is empty.
Integer division // is suitable for calculating a middle index.