Linear Search
Programmers often want to search through an array and see if a value is contained within it. For example find a pupil who's name is Bart. The easiest way to do this is to perform a linear search. A linear search checks each item in the array from first to last for the specified value.
One big advantage of the linear search is that the data does not need to be sorted.
However, one disadvantage is that it will be slow if the data you are looking for is in a large array and the search item you are looking for is at the end of the array. For example, if you were looking for "zebra" in an english dictionary starting at the beginnning.
Linear Algorithm Steps
Let's use the example of finding the name "Bart" in an array called names.
- Start at the first item in the array
Names[0].
- Compare the value of
Names[0]
against the name we are looking for. IsNames[0]
equal to "Bart." - If the name is the same, we have found the name and can stop. We might print "name found" or the position found.
- If the name is not the same, check the next value in the array...
Names[1]
. - Continue until the name is found or we have reached the last value in the array.
- If we get to the end and the name is not found, then the name did not exist in the array.
Coding the Linear Search
The code shown here does the following:
- Create an array called Names and set the values to some names.
- Use a count controlled loop to step through each value one at a time. Inside the loop:
- Check the current value of the names array against "Bart"
- If the name is found set a boolean variable to true and stop the loop.
- Check the boolean variables. If it hasn't been set to true the name has not been found.