Linear Search - Records
Purpose
The Linear Search algorithm looks through a list of items and finds if a value is in the list. It checks every item in the list and compares it to the search item.
After the algorithm has traversed the entire list then it will usually display an output message.
Record StructureÂ
All record examples will use this record structure:
And we have made an array called pupils which contains 40 of these pupil records.
Basic Linear Search PseudocodeÂ
SearchName = Input from user
FOR counter FROM 0 TO length(pupils)
IF array[counter].name = SearchItemÂ
Display “Item found”
END IF
END FOR
Basic Linear Search - Python
This simply traverses an array and displays a message if a match is found. But what if a match is not found?
Linear Search with Found Flag
We can improve the algorithm by using a Boolean flag to store whether a match has been found or not. As it is possible to search through a list and not find the item we are looking for. This boolean value will only be set to True if an item has been found. We can also store the position of the item found - as it may be useful to return this to index parallel arrays/records.
Linear Search with Found Flag - Pseudocode
choice = Input from user
found = FALSE
FOR counter FROM 0 TO length(array)
       IF array [counter].mark = choice:
          found = TRUE
          position = counter
END IF
END FOR
Linear Search with Found Flag - Python
We set up found as FALSE and then traverse the array using a fixed loop.Â
Then if we find the value we are looking for we set the found flag to TRUE.
Linear Search Using a Conditional Loop
A further improvement would be to utilise a conditional loop and a found flag. This will allow the algorithm to stop traversing through the loop when a match has been found.
The condition will to be continue the loop until either an item has been found or there are still items in the list. Meaning for more efficient code due to less operations required…unless the search item is at the end of the list.
Linear Search Using a Conditional Loop - Pseudocode
choice = Input from user
found = FALSE
counter = 0
WHILE counter <len(pupils) AND found = FALSE
       IF array [counter].name = choice:
          found = TRUE
          position = counter
END IF
counter = counter +1
END WHILE
The WHILE loop will carry on looking through the array as long as counter isn't past the end of the array and the found variable is false.
This means the loop will stop when the item is found or it finds a match. So is more efficient than the previous examples.
Linear Search Using a Conditional Loop - Python
Linear Search - Conditional Loop/Function without Found flag
Another method useful for a linear search is to just return the found position, but using the value -1 as the default. That way you know that if the foundpos is still equal to -1 after you have finished traversing through the array then you haven't found a match.