Linear Searching

Facebooktwitterredditpinterestlinkedinmailby feather

Searching

In the data structure, searching is the process in which an element is searched in a list that satisfies one or more than one condition.

Types of searching

There are two types of searching in the data structure.

  1. Linear searching
  2. Binary searching

Linear searching

In this searching technique, the searching element is compared one by one with each element of the list until the element is found. It is also called sequential searching.

In this, the searching element is compared with the first element of the list. If both the elements are the same, it returns the index value of that element. Otherwise, it returns -1. Similarly, the entire list is compared until the searching element is found. If the element is not found even after comparing the entire list, the searching prints “unsuccessful” message.

It is a very simple searching technique, but it takes a lot of time because the average-case complexity of the linear search is O (n).

Complexity of Linear searching

Complexity Best case Average case Worst case
Time O(1) O(n) O(n)
Space     O(1)

Algorithm of Linear searching

Linear_searching(A, N, VAL) Step 1: SET FLAG = -1 Step 2: SET I = 1 Step 3: Repeat step 4 while I<=N Step 4: if A[I] = VAL
            SET FLAG = I
            print “index value of the element”
            go to step 6
            // end of if
            SET I = I + 1
            // end of loop Step 5: if FLAG = -1
            print ” element is not found in this list “
            // end of if Step 6: exit  

For example, suppose you have the following array, and you have to search 30 in it.

Step 1: The given element (30) is compared with the first element (11) of the array.                                               11 ≠ 30              Both elements are not the same. Now, it will go to the next element.   Step 2: The given element (30) is compared with the second element (54) of the array.                                               54 ≠ 30              Both elements are not the same. Now, it will go to the next element. Step 3: The given element (30) is compared with the third element (45) of the array.                                               45 ≠ 30              Both elements are not the same. Now, it will go to the next element.   Step 4: The given element (30) is compared with the fourth element (30) of the array.                                               30 = 30              The given element is found, so it will stop comparing. It returns the index value, that is 3.

Linear search program in C language

#include<stdio.h>    void main ()   {       int a[10] = {15, 13, 40, 51, 32, 80, 14, 13, 57, 19};       int element, i, flag;       printf(“\n enter the searching element \n”);       scanf(“%d”,&element);       for (i = 0; i< 10; i++)       {           if(a[i] == element)            {               flag = i+1;               break;  
        }            else            flag = 0;       }        if(flag != 0)       {           printf(“\n element found and index value is %d\n”,flag);       }       else       {           printf(“\n element not found\n”);        }   }     

Output

enter the searching element 40 element found and index value is 2
Facebooktwitterredditpinterestlinkedinmailby feather