Linear search
Linear search looks through an array one item at a time until the target value is found, or the array ends. When a match is found, the algorithm records the position (index) where the item is stored. This position can then be displayed straight away (for example, “Found at position 3”) or it can be stored in a variable so that the program can use it later.
There are two main versions of linear search:
- Search for all occurrences
- This version continues searching the array until the very end, even if a match has already been found.
- It is used when the same value might appear more than once and you need to know the position of every match.
- Example use: finding every student who scored grade “A” in a class results array.
- Search for the first occurrence
- This version stops as soon as a match is found, without checking the rest of the array.
- It is used when all values in the array are unique, or when you only care about the first time a value appears.
- Example use: finding the first available seat in a booking system.
Example Code
array = [5, 8, 3, 8, 2]
target = 8
for i in range(len(array)):
if array[i] == target:
print("Found at position", i)
# Example array to search
array = [5, 8, 3, 8, 2]
# The value we are searching for
target = 8
# Go through every element in the array, one at a time
for i in range(len(array)):
# Check if the current element matches the target
if array[i] == target:
# If it matches, display the position (index number)
print("Found at position", i)
array = [5, 8, 3, 8, 2]
target = 8
found = False
pos = 0
while found == False and pos < len(array):
if array[pos] == target:
found = True
else:
pos = pos + 1
if found == True:
print("Found at position", pos)
else:
print("Not found")
# Example array to search
array = [5, 8, 3, 8, 2]
# The value we are searching for
target = 8
# A flag to say if the value has been found
found = False
# Position counter, starting at the first element
pos = 0
# Keep going until the value is found OR we reach the end of the array
while found == False and pos < len(array):
# Check if the current element matches the target
if array[pos] == target:
# If a match is found, change the flag to True
found = True
else:
# If not a match, move to the next position
pos = pos + 1
# After the loop, check if we found the target
if found == True:
print("Found at position", pos)
else:
print("Not found")