Last Updated:

Linear search algorithm

To find some element (key) in a given unordered array, a linear (sequential) search algorithm is used. It works with both unsorted and sorted arrays, but for the latter, there are algorithms more efficient than linear search.

This inefficiency is compensated by the simple implementation of the algorithm and the very possibility of applying it to disordered sequences. Here, as well as when considering all other search algorithms, we will assume that the key is a certain quantity, as the algorithm is executed, compared precisely with the values of the elements of the array.

The word "consistent" contains the main idea of the method. Starting with the first, all elements of the array are sequentially viewed and compared with the desired one. If at some step the current element is equal to the one sought, then the element is considered found, and the result is returned the number of this element, or other information about it. (Next, the result will be the number of the element). Otherwise, something should be returned that may indicate its absence in the sequence passed.

Below, on the example of figures, the work of the linear search algorithm is clearly demonstrated. The desired element (in this case, a square) is given a figure, and it is compared alternately with all the available figures until an identical figure is found, or it turns out that there is no such figure in this set.

Linear search algorithm

It is noteworthy that there is a possibility that there are several elements with the same values that match the value of the key. In this case, if there are no specific conditions, you can, for example, take the number of the first element found as the result (implemented in the listing below), or write the numbers of all identical elements to the array.

The code of the program in C++:

The code of the program in Pascal:

At best, when the desired element occupies the first position, the algorithm will make only one comparison, and at worst, N, where N is the number of elements in the array. Two situations correspond to the worst case: the desired element occupies the last position, or it is completely absent in the array.

 

The linear search algorithm is not often used in practice, since the principle of working "head-on" makes the speed of solving the problem very low. Its use is justified on small and / or unsorted sequences, but when the sequence consists of a large number of elements, and it has to be worked with more than once, then the most optimal solution is to pre-sort this sequence with the subsequent use of a binary or other, different from the linear, search algorithm.