Standard Searching Algorithms Ocr

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?