We’ll talk about the linear search algorithm in this article. Finding a certain element in the list is the process of searching. The procedure is considered effective and returns the element’s location if the element is contained in the list, if not, the search is considered failed.
Binary search and linear search are two frequently used search techniques. Therefore, we shall talk about the widely used linear search algorithm here.
Linear Search
A sequential search algorithm is another name for linear search. It is the most straightforward search algorithm. In a linear search, we just go through the list in its whole and match each element with the item whose position has to be found. The algorithm returns the item’s location if a match is made; otherwise, it returns NULL.
It is frequently used to search for a certain element in an unordered list or a list where the entries are not sorted. The linear search’s worst-case time complexity is O(n).
Steps of Linear Search
The steps used in the implementation of Linear Search are listed as follows –
First, we have to traverse the array elements using a for loop.
In each iteration of for loop, compare the search element with the current array element, and –
If the element matches, then return the index of the corresponding array element.
If the element does not match, then move to the next element.
If there is no match or the search element is not present in the given array, return -1.
Now, let’s see the algorithm of linear search.
Linear Search Algorithm:
let’s say the array is X and the value is i;
- Set j to 1
- If j > n, jump to step 7
- If X[j] == i, jump to step 6
- Then, increment j by 1 i.e. j = j+1
- Go back to step 2
- Display the element i which is found at particular index i, then jump to step 8
- Display element not found in the set of input elements.
- Exit/End
How Linear Search Algorithm Work?
To find an element in the list below with the value k = 1, follow these steps.
Array to be searched for
-
Compare each element x with k starting with the first element.
-
Return the index if x == k.
-
Else, return not found.
C Program Code for Linear Search
#include <stdio.h> int LINEAR_SEARCH(int inp_arr[], int size, int val) { for (int i = 0; i < size; i++) if (inp_arr[i] == val) return i; return -1; } int main(void) { int arr[] = { 10, 20, 30, 40, 50, 100, 0 }; int key = 100; int size = 10; int res = LINEAR_SEARCH(arr, size, key); if (res == -1) printf("ELEMENT NOT FOUND!!"); else printf("Item is present at index %d", res); return 0; }
Linear Search Complexities:
Time complexity: O(N) will be the time complexity for performing linear search.
Space complexity: O(1) will be the space complexity for performing linear search.
With this, we come to the end of this blog on ‘Linear Search in C’. I hope you found it informative.
Other C Programs
C Program for Binary Search
C Program to Add Two Numbers
C Program to Calculate Percentage of 5 Subjects
C Program to Convert Binary Number to Decimal Number
C Program to Convert Celsius to Fahrenheit
C Program to Convert Infix to Postfix
C Program to Find Area of Circle
C Program to Find Roots of Quadratic Equation
C program to Reverse a Linked List
C program to reverse a number
Ascending Order Program in C
Menu Driven Program For All Operations On Doubly Linked List in C
C Program for Armstrong Number
C Program For Merge Sort For Linked Lists
C program for performing Bubble sort on Linked List
Hello World Program in C
Perfect Number Program in C
Leap Year Program in C
Odd Even Program in C
Selection Sort Program in C