Linear Search

Linear Search

Sequential/Linear search

The simplest search technique is the sequential search. In this technique we start at the beginning of the list / array / table / file and search for the desired element by matching the value with each record being traversed, the process is continued till either the desired record is found or list is completely traversed.

This technique is suitable for a table which is arranged in the form of an array or linked list. This search may be improved if the list is ordered / sorted.

Advantages and disadvantages of Linear search

Advantages:

  • The linear search is simple
  • It is very easy to understand and implement
  • It does not require the data in the array to be sorted in any particular order.
  • It is memory efficient.

 Disadvantages

  • The linear search in inefficient.
  • It is slower
  • It needs more space and time complexity.

Algorithm

Case: 1
When the array elements are not sorted

Sequential_search(A,N,NUM)
A: Array containing elements (unsorted)
N: Total number of elements
NUM: element to search

Step no Process
1.   Set i=0
2.    Repeat steps 3,4 while (i<N)
3     If(A[i]=NUM) then
        Display “Element is present”
        Goto step 6
        [end of if block]
4   Set i=i+1
5   Display “Element is not present”
6   Return

Algorithm
Case:2
When the array elements are sorted

Sequential_search(A,N,NUM)
A: Array containing elements (sorted)
N: Total number of elements
NUM: element to search
Step no Process
1.   Set i=0
2.   Repeat steps 3,4 and 5 while (i<N)
3    If (A[i]>NUM) then
      Goto step 6
      [end of if block]
4    If(A[i]=NUM) then
      Display “Element is present”
      Goto step 7
      [end of if block]
5   Set i=i+1
6    Display “Element is not present”
7   Return

The complexity of the search algorithm is given by the number of comparisons between the element to search and the array elements.

Best Case :

The desired element is present in the first position of the array, i.e. only one comparison is made. So c(n)=O(1)

Worst case:

The worst case occurs when the element to search is the last element in the array or it is not present in the array. Then the number of comparisons will be “n” so the complexity is order of n i.e. O(n).

Average Case:

If the element to search is present ,then it is possible that it may be present at any location, so the of comparisons can be any of the following

1,2,3,4.. . . . n and each number occurs with the probability p=1/n

So

Total number of comparisons amount to

 C(n)=1/n + 2/n + 3/n + . . . . n/n

 = (1+2+3+ . . . +n)* 1/n

=n*(n+1)/2 * 1/n

= (n+1)/2

 Thus the average number of comparisons needed to find an element is approximately equal to half the number of elements in the array.

Linear Search C Implementation      Linear Search C++ Implementation