Embedded Files
Purpose
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. You have to bear in mind that a match MAY NOT be found.
Basic Linear Search Pseudocode
Basic Linear Search Pseudocode
SearchItem = Input From User
FOR counter FROM 0 TO length(array)
IF array[counter] = SearchItem
DISPLAY “Item found”
END IF
END FOR
Basic Linear Search - Python
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
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 will only be set to True when 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
Linear Search with Found Flag - Pseudocode
choice = Input from User
found = FALSE
FOR counter FROM 0 TO length(array)
IF array [counter] = choice:
found = TRUE
position = counter
END IF
END FOR
Linear Search with Found Flag - Python
Linear Search with Found Flag - Python
We set up a position counter 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
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
Linear Search Using a Conditional Loop - Pseudocode
choice = input from USER
found = FALSE
counter = 0
WHILE counter <len(names) AND found = FALSE
IF array [counter] = 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 a more efficient algorithm than the previous examples.
Linear Search Using a Conditional Loop - Python
Linear Search Using a Conditional Loop - Python
Linear Search - Conditional Loop/Function without Boolean value
Linear Search - Conditional Loop/Function without Boolean value
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 foundpos = -1 then a match was not found in the list.
This is an import consideration as a Linear Search may not always find a match.
Tutorial Video - Linear Search
Tutorial Video - Linear Search
8 - Linear Search.mp4Page updated
Report abuse