Linear 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 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
|
| 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 |
Exam Tip
You will not be asked to perform a linear search on a dataset in the exam, you will be expected to understand how to do it and know the advantages and disadvantages compared to a binary search
Worked example
A linear search could be used instead of a binary search.
Describe the steps a linear search would follow when searching for a number that is not in the given list [2]
Answer
- Starting with the first value
- Checking all values in order
Guidance
- Must cover idea of checking all value AND being done in order!
- "Checks each value from the beginning to the end" implies order so would get both bullet point 1 & 2
A linear search in python
# Identify the dataset to search, the target value and set the initial flagdata = [5, 2, 8, 1, 9]target = 11found = False
# Loop through each element in the datafor 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 messageif found is False: print("Target not found")
