Linear Search is a simplest searching algorithm that goes through all the elements in sequence from start to end. In linear search, the algorithm checks every single element whether it’s a required element or not.
This searching technique can be applied to sorted or unsorted lists or arrays.
The algorithm is as follows:
• Start searching from the leftmost element of arr[] and one by one compare x with each element of arr[]
• If x matches with an element, return the index.
• If x doesn’t match with any of the elements, return -1.
{
int i;
for (i = 0; i < n; i++)
if (arr[i] == x)
return i;
return -1;
}
int main(void)
{
int arr[] = { 9, 4, 45, 75, 16, 15, 23, 54, 79 };
int x = 23;
int n = sizeof(arr) / sizeof(arr[0]);
int result = search(arr, n, x);
if(result == -1)
printf("Element not present.");
else
printf("Element is present at index %d", result); return 0;
}
This searching technique can be applied to sorted or unsorted lists or arrays.
For Example:
Let us consider an unsorted array of size 9. The following image consists of the elements in the array. Now we need to find the exact position/place of element “20”.The algorithm is as follows:
• Start searching from the leftmost element of arr[] and one by one compare x with each element of arr[]
• If x matches with an element, return the index.
• If x doesn’t match with any of the elements, return -1.
Program Code
#include <stdio.h>
int search(int arr[], int n, int x) {
int i;
for (i = 0; i < n; i++)
if (arr[i] == x)
return i;
return -1;
}
int main(void)
{
int arr[] = { 9, 4, 45, 75, 16, 15, 23, 54, 79 };
int x = 23;
int n = sizeof(arr) / sizeof(arr[0]);
int result = search(arr, n, x);
if(result == -1)
printf("Element not present.");
else
printf("Element is present at index %d", result); return 0;
}
Output:
Element is present at index 6.
The Time Complexity of Linear Search Algorithm is O(n). That means the time taken to search will directly be dependent on the size of the array or list. Nowadays, in a practical scenario, Linear search is rarely used. Because of some faster searching algorithms discovered like, Binary Search and Hashing Tables, which eventually takes lesser time to search any data from arrays or lists.