# 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.

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++:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 | #include "stdafx.h" #include <iostream> #include <ctime> using namespace std; int i,N; //linear search int LineSearch(int A[], int key) { for (i=0; i<N; i++) if (A[i]==key) return i; return -1; } // main function void main() { setlocale(LC_ALL,"Rus"); intkey, A[1000]; srand(time(NULL)); cout<<"Array size>"; cin>>N; cout<<"Searched element> "; cin>>key; cout<<"Source array: "; for (i=0; i<N; i++) { A[i]=rand()%10; cout<<A[i]<<" "; } if (LineSearch(A, key)==-1) cout<<"\nElement not found"; else cout<<"\nElement number: "<<LineSearch(A, key)+1; system("pause>>void"); } |

### The code of the **program in Pascal**:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 | program linearSearch; usescrt; type Arr=array[1..1000] of integer; var key, i, N: integer; A: Arr; {linear search} function lineSearch(A: Arr; key: integer): integer; begin lineSearch:=-1; for i:=1 to N do if A[i]=key then beginlineSearch:=i; exit; end; end; {main program block} begin randomize; write('Array size > '); readln(N); write('Search item > '); read(key); write('Source array: '); for i:=1 to N do begin A[i]:=random(10); write(A[i],' '); end; writeln; if (lineSearch(A, key)=-1) then write('Element not found') else write('Element number: ', lineSearch(A, key)); end. |

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.