Standard Searching Algorithms (OCR 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")

Linear Search

What is a linear search?

• A linear search starts with the first value in a dataset and checks every value one at a time until all values have been checked

• A linear search can be performed even if the values are not in order

How do you perform a linear search?

What are the advantages and disadvantages of searching algorithms?

A linear search in python

# Identify the dataset to search, the target value and set the initial flag
data = [5, 2, 8, 1, 9]
target = 11
found = False

# Loop through each element in the data
for index in range(0,len(data)):
  
  # Check if the current element matches the target
  if data[index] == target:
    
    # If found, output message
    found = True
    print("Target found")

#If the target is not found, output a message
if found is False:
  print("Target not found")