Searching in Linear Array Algorithm

In linear search algorithm, a sequential search is made over all items one by one. Every item is checked and if a match is found then that particular item is returned, otherwise the search continues till the end of the data collection.


Suppose A is a linear array with n elements. Given no other information about A, the most intuitive way to search for a given ITEM in A is to compute ITEM with each element of A one by one. That is, first we test whether A[1] = ITEM, and then we test whether A[2] = ITEM, and so on. This method, which traverses A sequentially to locate ITEM, is called ‘linear search’ or ‘sequential search’.

Algorithm: (Linear Search.) LINEAR(A, N, ITEM, LOC).

Here, A is a linear array with N elements, and ITEM is a given item of information. This algorithm finds the location LOC of ITEM in A, or sets LOC := 0 if the search is unsuccessful.

Step I: [Insert ITEM at the end of A.]
Set A[N+1] := ITEM.
Step II: [Initialize counter.]
Set LOC := 1.
Step III: [Search for ITEM.]
Repeat while A[LOC] != ITEM.
Set := LOC := LOC+1.
[End of step 3 loop.]
Step IV: [Successful?]
If LOC := N+1, then:
  Print LOC := NULL.
Else:
Print LOC.
Step V: Exit.