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

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?

Step	Instruction
1	Check the first value
2	IF it is the value you are looking for STOP!
3	ELSE move to the next value and check
4	REPEAT UNTIL you have checked all values and not found the value you are looking for

What are the advantages and disadvantages of searching algorithms?

Searching Algorithm	Advantages	Disadvantages
Binary search	Fast for large datasets Efficient for repeated searches	Dataset must be in order More complex to implement
Linear search	Works on unsorted datasets Faster (than binary) on very small datasets Simple to understand and implement	Slow for large datasets Inefficient, starts at the beginning each time

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) - 1):
  
  # 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")