Linear search

Linear search or sequential search is a method to find an item in a list. It is a search algorithm.

Algorithm

Start out with a list, L which may have the item that we want to look for.

1. If the list L is empty, then the list has nothing. The list does not have the item that we are looking for, so we stop here.
2. If the list L is not empty, we look at all the elements in the list.
3. For each element:
   1. If the element equals the item that we are looking for, the list has the item in question, so we will stop here and return the position in the list that has the element that we are looking for.
   2. If not, we will go on to the next element.
4. When we reached the end of the list and still have not found the element that we are looking for, then the list does not have the item that we want.

Implementation

In the Java programming language, linear search looks like this. This method has two parameters: an array of integers and the item we are looking for (also an integer). It says the location in the array if it finds the item. If it does not find it, it says -1.

public int linearSearch(int[] list, int item) {
    for (int i = 0; i < list.length; i++) {
        if (list[i] == item) {
            return i;
        }
    }

    return -1;
}

Related pages

• Binary search
• Breadth-first search
• Depth-first search