Binary Search (AQA GCSE Computer Science)
Revision Note
Binary Search
What is a searching algorithm?
Searching algorithms are precise step-by-step instructions that a computer can follow to efficiently locate specific data in massive datasets
Two common searching algorithms are:
Binary search
Linear search
What is a binary search?
A binary search keeps halving a dataset by comparing the target value with the middle value, going left if smaller, right if bigger, until it finds the value or realises it's not there
To perform a binary search the data must be in order!
A binary search can be performed on datasets containing numbers or words.
Searching for a word instead of a number is the same process, except comparisons are made based on position in the alphabet (alphabetically) instead of numerical size
How do you perform a binary search?
Example 1 - numbers
Perform a binary search to locate number 7 in the following dataset
Example 2 - words
Perform a binary search to locate the word "Rock" in the following dataset
Examiner Tip
If the dataset has an even number of values, the simplest way to identify the middle is to divide the total values by 2 and use that as a middle value i.e. a dataset with 8 values, 4 would be the middle value
Worked Example
Describe the steps a binary search will follow to look for a number in a sorted list [4]
Answer
Select / choose / pick middle number (or left/right of middle as even number) and …
…check if selected number is equal to / matches target number (not just compare)
…if searched number is larger, discard left half // if searched number is smaller, discard right half
Repeat until number found
… or remaining list is of size 1 / 0 (number not found)
Guidance
Can get a mark for bullet points 1 & 2 in one step (e.g. check if the middle value is the one we're looking for")
A binary search in python
# Identify the dataset to search, the target value and set the initial flag
data = [2, 4, 6, 8, 10, 12, 14]
target = 8
found = False
# Set the initial low and high pointers to the beginning and end of the data
low = 0
high = len(data) - 1
# While the low pointer is less than or equal to the high pointer
while found is False and low <= high:
# Find the middle index
mid = (low + high) // 2
# Check if the target is at the middle index
if data[mid] == target:
# If the target is found, output a message
found = True
print("Target found")
# If the target is less than the middle value, search in the left half of the data
elif data[mid] > target:
high = mid - 1
# Otherwise, search in the right half of the data
else:
low = mid + 1
# If the target is not found, output a message
if found is False:
print("Target not found")
Last updated:
You've read 0 of your 10 free revision notes
Unlock more, it's free!
Did this page help you?