Binary Search (AQA GCSE Computer Science)

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... Stop!
4	ELSE IF is it bigger than the one you are looking for... Create a new list with the values on the left of the middle value
5	IF it is smaller than the one you are looking for... Create a new list with the values on the right of the middle value
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 5 7 12 15 22 46
2	Compare to the value you are looking for - Is 12 == 7?
3	IF it is the value you are looking for... Stop! - 12 is not equal to 7
4	ELSE IF is it bigger than the one you are looking for... Is 12 > 7? YES Create a new list with the values on the left of the middle value 2 5 7
5	IF it is smaller than the one you are looking for... Create a new list with the values on the right of the middle value
6	REPEAT with the new list 2 5 7 Is 5 == 7? NO Is 5  > 7? NO - create new list with values to the right 7 Is 7 == 7? YES 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")
	Ballroom Country Electronic Hip Hop Jazz Rock Techno
2	Compare to the value you are looking for - Is "Hip Hop" == "Rock"?
3	IF it is the value you are looking for... Stop! - "Hip Hop" is not equal to "Rock"
4	ELSE IF is it bigger than the one you are looking for... Is "Hip Hop" > "Rock"? NO Create a new list with the values on the left of the middle value
5	IF it is smaller than the one you are looking for... Is "Hip Hop" < "Rock"? YES Create a new list with the values on the right of the middle value Jazz Rock Techno
6	REPEAT with the new list Jazz Rock Techno Is "Rock" == "Rock"? YES STOP!

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")