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

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