Linear Search - W3colleges

In this tutorial, you will learn about linear search.

Linear search is a very simple and basic search algorithm. It is basically a sequential search algorithm. We have to write a C Program which finds the position of an element in an array using Linear Search Algorithm.

Examples :

Input : arr[] = {40, 60, 10, 20, 50, 30}
          x = 50;
Output : 4
Given element is present at index 4

Input : arr[] = {40, 60, 10, 20, 50, 30}
          x = 80;
Output : -1
Given element x is not present in arr[]

Linear Search Algorithm :

LinearSearch(array, key)
  for each item in the array
    if item == value
      return its index

Implementation :

#include <stdio.h> 
 
 // linear search function 
int LINEAR_SEARCH(int inp_arr[], int size, int val) 
{ 
    
     // scan entire array
    for (int i = 0; i < size; i++) 
        if (inp_arr[i] == val) 
        
            // return index number if found
            return i;
            
    // return -1 if not found        
    return -1; 
} 
 
 // driver program
int main(void) 
{ 
    // take array
    int arr[] = {40, 60, 10, 20, 50, 30}; 
    
    // take key to be searched
    int key = 50; 
    
    // take size of array
    int size = 6; 
    
    // call linear search function 
    // and store its retured value
    int res = LINEAR_SEARCH(arr, size, key); 
    
    // now print returned value 
    if (res == -1)
    printf("Given element x is not present in arr[]");
    else
    printf("Given element is present at index %d", res);
     
     // successfull completion
    return 0; 
}

Output :

Given element is present at index 5

Average, Best, and Worst cases :

Average Case:
If the searched element is other than the first and the last element of the array.

For example:
```
Input : arr[] = {40, 60, 10, 20, 50, 30};
          x = 50;
Output : 4 
```
Average case time complexity: O(n)
Best Case:
If the searched element is the first element of the array.

For example:
```
Input : arr[] = {40, 60, 10, 20, 50, 30};
          x = 40;
Output : 1 
```
Best case time complexity: O(1)
Worst Case:
If the element searched for is the last element of the array.
For example:
```
Input : arr[] = {40, 60, 10, 20, 50, 30};
          x = 30;
Output : 5 
```
Worst case time complexity: O(n)

Please write comments if you find anything incorrect. A gentle request to share this topic on your social media profile.