OCR J277 2.1 / AQA 8525 algorithms
Search a sorted list using low, high and mid pointers.
← All GCSE Python lessonsBinary search repeatedly compares the target with the middle item and discards the half that cannot contain it. The input must be sorted for that decision to be valid. Test first, middle, last and absent targets to check the boundary updates.
Watch out: Incorrectly changing low or high can skip a remaining item or cause an infinite loop. Trace both limits.
Read this worked example. Predict its output, run it in Python 3, and explain how variables change.
def binary_search(values, target):
low, high = 0, len(values)-1
while low <= high:
mid = (low + high) // 2
if values[mid] == target:
return mid
if values[mid] < target:
low = mid + 1
else:
high = mid - 1
return -1
print(binary_search([2, 4, 6, 8, 10], 8))Search a sorted list using low, high and mid pointers. Work from the starter code before comparing with the solution.
Download starter + solution ZIP ↓For a stretch challenge: add meaningful test data, handle an edge case and explain one design decision.
def binary_search(values, target):
low, high = 0, len(values)-1
while low <= high:
mid = (low + high) // 2
if values[mid] == target:
return mid
elif values[mid] < target:
low = mid + 1
else:
high = mid - 1
return -1
numbers = [2, 4, 6, 8, 10, 12]
for target in [2, 11, 12]:
print(target, binary_search(numbers, target))The reference is one possible approach. Test your own program before comparing.
Question: What happens if the input list is unsorted?
We cannot know which half to discard, so results may be wrong.
Explain one test you used, one problem you solved and one improvement you would make.
This records completion only in this browser and does not certify mastery.
Want extra practice? Try interactive Python tracing and debugging questions →