
The linear search algorithm is a very simple and straightforward in data structure. A linear search is also known as a sequential search. If the list or array is unordered, the linear search is preferable.
Linear search is an excellent approach to find elements, however we must check each element of the array or list in this search. As a result, the program’s speed slows down in comparison to others.
Table of Contents
How does linear search work?
The search begins sequentially, with the leading element being compared to the entries in the list. We check each item in the list and return a flag if a match is found; otherwise, we keep searching until we reach the end of the list or array.
Linear search algorithm Steps
We can cover the full searching with only 6 steps since the steps of the sequential search are so simple.
- Step 1: Take the first element from the list which will be the current element.
- Step 2: Make a comparison between the current element and the key element. If both are same, go to step 5.
- Step 3: If the next element is present in the list, consider it as the current element and got to Step 2.
- Step 4: If key element not found in list. Go to step 6.
- Step 5: Key element found then return location or flag.
- Step 6: Exit of the Algorithm.
Pseudocode of Linear search algorithm
search (array, key) for item in the array if match item == key then return the flag; end if end for end of search
Linear search program in C using array
#include <stdio.h>
#define MAX 7
int lrSearch(int arr[], int keyElement) {
int i = 0;
for (i = 0; i < MAX; i++) {
if (arr[i] == keyElement) {
return i;
}
}
return -1;
}
int main() {
int arr[] = {
11,
21,
31,
41,
51,
61,
71
};
int keyElement = 31;
printf("Position of element %d is %d\n", keyElement, (lrSearch(arr, keyElement) + 1));
return 0;
}
Output: Position of element 31 is 3
Different program of Linear search in C
#include <stdio.h>
#define MAX 7
void linear_search(int list[], int keyElement) {
int i, flag = 0;
for (i = 0; i < MAX; i++)
if (list[i] == keyElement) {
printf("\nThe element %d is present at position %d in list\n", keyElement, i);
flag = 1;
break;
}
if (flag == 0) {
printf("\nThe element %d is not present in the list\n", keyElement);
}
}
void printlist(int list[]) {
int i;
printf("The elements of the list are: \n");
for (i = 0; i < MAX; i++) {
printf("%d\t", list[i]);
}
}
void main() {
int list[MAX] = {
10,
11,
12,
13,
15,
16,
17
}, n, keyElement = 16;
printf("\nThe list before sorting is:\n");
printlist(list);
linear_search(list, keyElement);
}
Output: The list before sorting is: The elements of the list are: 10 11 12 13 15 16 17 The element 16 is present at position 5 in list
Linear search algorithm Time Complexity
Because the search time is proportional to the number of comparisons required, this will typically do about n/2 comparisons.
- Worst Case Complexity of Linear Search is O(n).
- Average Case Complexity of Linear Search is O(n).
- Best Case Complexity of Linear Search is O(1).
Linear search algorithm Space Complexity
Space Complexity of Linear Search is O(1).
In conclusion, When the number of entries in the list is small, we should use the linear (sequential) search approach.