Linear Search
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.
- Linear searching
- 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