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 of first row i.e 23 of the list, but 45 is not equal to 23. So move to next element i.e. 2nd element of first row of the list.
Step 2: Item 45 is compared with second element of first row i.e. 45 of the list, and 45 is equal to 45. So Print “Found at location row 1st column 2nd” 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 of first row i.e 23 of the list, but 40 is not equal to 23. So move to next element i.e. 2nd element of first row 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. But there is no third element in the first row. So move to second row.
Step 3: Item i.e. 40 is compared with first element of 2nd row i.e 32 of the list, but 40 is not equal to 32. So move to next element i.e. 2nd element of the 2nd row of the list.
Step 4: Item i.e. 40 is compared with 2nd element of 2nd row i.e 21 of the list, but 40 is not equal to 21. So move to next element but no more elements in the row are there. So move to next row. But no more rows are available.
Step 5: Print “Item is not found in the list”
Algorithm for linear Search
linear_search(a,m,n) where a is the array having m rows and n columns.
- for(i=0;i<m;i++)
- for(j=0;j<n;j++)
- if(item==a[i][j])
- {
- printf(“item found at location %d”,i+1);
- return;
- }
- printf(“item not found “);
Time Complexity: O(mn) where m is the number of rows and n is the number of columns in two dimensional array.
Space Complexity: O(1)
Program for linear Search (Without Using Function)
#include <stdio.h>
int main()
{
printf("******************************************\n");
printf("******************************************\n");
printf("* Linear Search Program Without Function *\n");
printf("* Created by Sheetal Garg *\n");
printf("* Assistant Professor *\n");
printf("* Phone No:9467863365 *\n");
printf("******************************************\n");
printf("******************************************\n");
int m,n, i, j, a[5][5], item;
printf("\nEnter no. of rows and columns in the array : ");
scanf("%d%d", &m, &n);
printf("enter array elements");
for (i = 0; i < m; i++)
for (j = 0; j < n; j++)
scanf("%d", &a[i][j]);
printf("enter the item to search : ");
scanf("%d", &item);
for (i = 0; i < m; i++)
for (j = 0; j < n; j++)
if (item == a[i][j])
{
printf("item found at Row : %d, column : %d", i+1, j+1);
return 0;
}
printf("Item not found");
return 0;
}
Output 1:
****************************************** ****************************************** * Linear Search Program Without Function * * Created by Sheetal Garg * * Assistant Professor * * Phone No:9467863365 * ****************************************** ****************************************** Enter no. of rows and columns in the array : 2 2 enter array elements 12 23 21 31 enter the item to search : 23 item found at Row : 1, column : 2
Output 2:
****************************************** ****************************************** * Linear Search Program Without Function * * Created by Sheetal Garg * * Assistant Professor * * Phone No:9467863365 * ****************************************** ****************************************** Enter no. of rows and columns in the array : 2 2 enter array elements 12 23 32 21 enter the item to search : 45 Item not found
Program for linear Search (Using Function)
#include <stdio.h>
void find(int a[][5], int m, int n, int item);
int main()
{
printf("****************************************\n");
printf("****************************************\n");
printf("* Linear Search Program Using Function *\n");
printf("* Created by Sheetal Garg *\n");
printf("* Assistant Professor *\n");
printf("* Phone No:9467863365 *\n");
printf("****************************************\n");
printf("****************************************\n");
int m,n, i, j, a[5][5], item;
printf("\nEnter no. of rows and columns in the array : ");
scanf("%d%d", &m, &n);
printf("enter array elements");
for (i = 0; i < m; i++)
for (j = 0; j < n; j++)
scanf("%d", &a[i][j]);
printf("enter the item to search : ");
scanf("%d", &item);
find(a, m, n, item);
return 0;
}
void find(int a[][5], int m, int n, int item)
{
int i, j;
for (i = 0; i < m; i++)
for (j = 0; j < n; j++)
if (item == a[i][j])
{
printf("item found at Row : %d, column : %d", i+1, j+1);
return;
}
printf("Item not found");
}
Output 1:
**************************************** **************************************** * Linear Search Program Using Function * * Created by Sheetal Garg * * Assistant Professor * * Phone No:9467863365 * **************************************** **************************************** Enter no. of rows and columns in the array : 3 3 enter array elements 12 34 54 32 56 76 12 32 13 enter the item to search : 54 item found at Row : 1, column : 3
Output 2:
**************************************** **************************************** * Linear Search Program Using Function * * Created by Sheetal Garg * * Assistant Professor * * Phone No:9467863365 * **************************************** **************************************** Enter no. of rows and columns in the array : 2 3 enter array elements 23 24 45 21 13 43 enter the item to search : 76 Item not found