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?
Step | Instruction |
1 | Identify the middle value |
2 | Compare to the value you are looking for |
3 | IF it is the value you are looking for...
|
4 |
ELSE IF is it bigger than the one you are looking for...
|
5 |
IF it is smaller than the one you are looking for...
|
6 | REPEAT with the new list |
Example 1 - numbers
- Perform a binary search to locate number 7 in the following dataset
2 | 5 | 7 | 12 | 15 | 22 | 46 |
Step | Instruction | |||||||
1 | Identify the middle value (12) | |||||||
|
||||||||
2 | Compare to the value you are looking for - Is 12 == 7? | |||||||
3 | IF it is the value you are looking for...
|
|||||||
4 |
ELSE IF is it bigger than the one you are looking for... Is 12 > 7? YES
|
|||||||
5 |
IF it is smaller than the one you are looking for...
|
|||||||
6 |
REPEAT with the new list
Is 5 > 7? NO - create new list with values to the right
STOP! |
Example 2 - words
- Perform a binary search to locate the word "Rock" in the following dataset
Ballroom | Country | Electronic | Hip Hop | Jazz | Rock | Techno |
Step | Instruction | |||||||
1 | Identify the middle value ("Hip Hop") | |||||||
|
||||||||
2 | Compare to the value you are looking for - Is "Hip Hop" == "Rock"? | |||||||
3 | IF it is the value you are looking for...
|
|||||||
4 |
ELSE IF is it bigger than the one you are looking for... Is "Hip Hop" > "Rock"? NO
|
|||||||
5 |
IF it is smaller than the one you are looking for... Is "Hip Hop" < "Rock"? YES
|
|||||||
6 |
REPEAT with the new list
STOP! |
Exam 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")