Searching It means to find the location of an item/element/value in an array/list. It will return or print the location of the item , if the item is present in the list/array, otherwise it will print “Not Found” or return a non valid index (say -1)
Linear Search It searches the element in the list by comparing it with each element of the list one by one, starting from begining to end. If the element is found, it returns or prints the index number of the element and stop searching. If we reach at the end of the list, and the element is not found, then it will print “Not Found” or return a non valid index (say -1)
Example 1: Suppose we have to find 45 in the list 23,45,32,21
Step 1: Item i.e. 45 is compared with first element i.e 23 of the list, but 45 is not equal to 23. So move to next element i.e. 2nd element of the list.
Step 2: Item 45 is compared with second element i.e. 45 of the list, and 45 is equal to 45. So Print “Found at location 2” and stop searching
Example 2: Suppose we have to find 40 in the list 23,45,32,21
Step 1: Item i.e. 40 is compared with first element i.e 23 of the list, but 40 is not equal to 23. So move to next element i.e. 2nd element of the list.
Step 2: Item i.e. 40 is compared with second element i.e 45 of the list, but 40 is not equal to 45. So move to next element i.e. 3rd element of the list.
Step 3: Item i.e. 40 is compared with third element i.e 32 of the list, but 40 is not equal to 32. So move to next element i.e. 4th element of the list.
Step 4: Item i.e. 40 is compared with forth element i.e 21 of the list, but 40 is not equal to 21. So move to next element but no more elemnts in the list are there
Step 5: Print “Item is not found in the list”
Algorithm for linear Search
linear_search(a,n) where a is the array having n elements.
- for(i=0;i<n;i++)
- if(item==a[i])
- {
- printf(“item found at location %d”,i+1);
- break;
- }
- if(i==n)
- printf(“item not found “);
Time Complexity: O(n)
Space Complexity: O(1)
Program for linear Search (Without Function)
#include<stdio.h>
int main()
{
printf ("****************************************************************");
printf ("\n****************************************************************");
printf ("\n** Program to search an item in an array using linear search **");
printf ("\n** Created by Sheetal Garg **");
printf ("\n** Assistant Professor **");
printf ("\n** Phone No:9467863365 **");
printf ("\n****************************************************************");
printf ("\n****************************************************************");
int n,i,a[5],item;
printf("\nEnter no. of elements in the array\n");
scanf("%d",&n);
printf("enter array elemnents");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
printf("enter the item to search");
scanf("%d",&item);
for(i=0;i<n;i++)
if(item==a[i])
{
printf("item found at location %d",i+1);
break;
}
if(i==n)
printf("item not found ");
return 0;
}
Output 1:
**************************************************************** **************************************************************** ** Program to search an item in an array using linear search ** ** Created by Sheetal Garg ** ** Assistant Professor ** ** Phone No:9467863365 ** **************************************************************** **************************************************************** Enter no. of elements in the array 4 enter array elemnents 23 45 32 21 enter the item to search 45 item found at location 2
Output 2:
**************************************************************** **************************************************************** ** Program to search an item in an array using linear search ** ** Created by Sheetal Garg ** ** Assistant Professor ** ** Phone No:9467863365 ** **************************************************************** **************************************************************** Enter no. of elements in the array 4 enter array elemnents 23 45 32 21 enter the item to search 40 item not found
Program for linear Search (With Function)
#include <stdio.h>
int findlocation(int a[], int n, int item);
int main()
{
printf("****************************************************************");
printf("\n****************************************************************");
printf("\n** Program to search an item in an array using linear search **");
printf("\n** Created by Sheetal Garg **");
printf("\n** Assistant Professor **");
printf("\n** Phone No:9467863365 **");
printf("\n****************************************************************");
printf("\n****************************************************************");
int n, i, a[5], item,loc;
printf("\nEnter no. of elements in the array\n");
scanf("%d", &n);
printf("enter array elemnents");
for (i = 0; i < n; i++)
scanf("%d", &a[i]);
printf("enter the item to search");
scanf("%d", &item);
loc = findlocation(a, n, item);
if (loc == 0)
printf("item not found ");
else
printf("item found at location %d", loc);
return 0;
}
int findlocation(int a[], int n, int item)
{
for (int i = 0; i < n; i++)
if (item == a[i])
return i + 1;
return 0;
}
Output 1:
**************************************************************** ** Program to search an item in an array using linear search ** ** Created by Sheetal Garg ** ** Assistant Professor ** ** Phone No:9467863365 ** **************************************************************** **************************************************************** Enter no. of elements in the array 5 enter array elemnents 23 34 66 54 54 enter the item to search23 item found at location 1
Output 2:
**************************************************************** **************************************************************** ** Program to search an item in an array using linear search ** ** Created by Sheetal Garg ** ** Assistant Professor ** ** Phone No:9467863365 ** **************************************************************** **************************************************************** Enter no. of elements in the array 4 enter array elemnents 23 45 32 21 enter the item to search 40 item not found