Linear search

To find a certain element (key) in a given unordered array, a linear (sequential) search algorithm is used. It works with both unsorted arrays and sorted ones, 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 ability to apply it to unordered sequences. Here, as well as when considering all other search algorithms, we will assume that a key is a certain value, as the algorithm is executed, which is compared with the values ​​of the array elements.

The word "consistent" contains the basic idea of ​​the method. Starting from the first, all elements of the array are sequentially reviewed and compared with the desired one. If at some step the current element is equal to the desired one, then the element is considered to be found, and the result is the number of this element or other information about it. (Further, the number of the element will be the output data). Otherwise, you should return something that may indicate its absence in the traversed sequence.

Below, by the example of figures, the work of the linear search algorithm is clearly demonstrated. As a required element (in this case, this is a square), a figure is specified, and it is compared in turn with all existing figures until a figure identical to it is found, or it turns out that there is no such set.

It is noteworthy that there is a probability of having several elements with the same values ​​that coincide with the key value. In this case, if there are no specific conditions, you can, for example, take the number of the first element found (shown in the listing below) as a resultant, or write the numbers of all identical elements into an array.

C ++ program code:

Pascal program code:

In the best case, when the desired element takes 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 work "in the forehead" makes the speed of solving a problem by it very low. Its use is justified on small and / or unsorted sequences, but when a sequence consists of a large number of elements and you have to work with it more than once, then the most optimal solution is to pre-sort this sequence followed by a binary or other non-linear search algorithm. .

See also