We have explored Linear Search algorithm and implemented variants of Linear Search in C Programming Language. The variants we have explored are:

• Linear Search in array in C
• Linear Search in Linked List in C
• Linear Search in array with duplicates in C
• Linear Search in Linked List with duplicates in C

Linear Search is a sequential search algorithm to find the position of a key in a given list of elements by traversing every element in the list until a match is found.

Though Linear search is the simplest searching technique, it is rarely used practically, since other searching algorithms like binary search are faster.

Algorithm

Compare every element with the key until there is a match. If match is found, return the position of element and stop. Else key not found in the list, return -1.

• Step 1 : Initialize current element with first element of the list.
• Step 2 : Compare current element with the key. If they are equal, goto Step 5
• Step 3 : Set next element, if present, as current element and goto Step 2
• Step 4 : All elements are traversed and no element of array matches key. So, key not found. Return -1
• Step 5 : Key is found. Return the position of the element

Example

Let us consider the following array or linked list with key as 12 :

8, 7, 9, 12, 10, 13, 18

• Iteration 0 : current element is 8

8, 7, 9, 12, 10, 13, 18
.^
current element != key
8!=12
Set next element if available, as current element

• Iteration 1 : Current element is 7

8, 7, 9, 12, 10, 13, 18
......^

current element != key
7!=12
Set next element if available, as current element

• Iteration 2 : Current element is 9

8, 7, 9, 12, 10, 13, 18
............^

current element != key
9!=12
Set next element if available, as current element

• Iteration 3 : Current element is 12

8, 7, 9, 12, 10, 13, 18
..................^

current element == key (match found)
12==12
Key is found at 3rd position. So we stop the process

Complexity

• Worst case time complexity: Θ(N)
• Average case time complexity: Θ(N)
• Best case time complexity: Θ(1)
• Space complexity: Θ(1)

If n is the number of elements in the given list, in Best Case the key may be present as the first element, requiring only 1 comparison.
In the Worst Case the key may be present as the last element or may not be found in the input list at all, so we would have to traverse the entire list, leading to n comparisons

In the Average Case it takes n/2 comparisons.

How to put the algorithm in action ? :

We need to define a function that takes the array and the key as input and returns the position of the key, if present or -1. The crux of the algorithm is that we need to traverse element by element (linearly) and compare the element with the key, until current element and the key match. Once we find such an element in our array, we can stop iterating over the rest of the elements and return the position of the current element.

Implementation in C:

Linear search in given array :

#include <stdio.h>
#include <stdlib.h>
/*
Input : integer array indexed from 0, key to be searched
Ouput : Position of the key in the array if found, else -1
*/
int linearSearch(int a[], int n, int key) {
int pos = -1;
for (int i = 0; i < n; ++i) {
    if (a[i] == key) {
    pos = i;
    break;
    }
}
return pos;
}

int main() {
int a[] = {8, 12, 3, 4, 7, 2, 13};
int n = sizeof(a) / sizeof(a[0]);
int pos = linearSearch(a, n, 3);
if (pos != 1)
    printf("Key found at position : %d \n", pos);
else
    printf("Key not found \n");
return 0;
}

Output :

    
 Key found at position : 2

How the above C code works?

Let us look at the function linearSearch(). It takes in 3 parameters :

• input array
• size of array
• the key that we need to search for.

We have a for loop inside this function, which iterates from index 0 until end of the array (index n-1). Next, we have a check during every iteration, if the current element is equal to the key, using an if condition. If there is a match, store the position of the element(index) and stop the for loop using a break statement and return the position. Otherwise keep iterating over the rest of the elements until the if condition becomes true.

Suppose the control never reaches inside the if condition, that is, if for every element in the array, the if condition fails, then our pos variable never gets updated. Essentially, its value remains as -1 (the value when we initialized it in the beginning). At the end of the for loop, if our pos value remains as -1, it would mean that the key could not be found in the given array.

NOTE : You can even directly return the position (i) inside the if condition instead and return -1 instead of pos at the end of the function

Linear Search in given Linked List

How to put the algorithm in action?

We need to define a function that will take as input the key to be searched in the linked list. Then we need to traverse the linked list till we find the node with the same data as the key.

Once we find the match, we can return the position of the node in the linked list. But how do we return the position of the node when there is no concept of indexing in linked list ? We just need to maintain an extra variable to keep count of the number of nodes traversed, which will give us the position. So everytime we traverse through a node, we increment the counter variable. Once we find the node with the same data as the key, we return that counter variable as the position of the key ! As you can see, the logic here is the same as for linear search in an array.

If no node in the entire linked list has its data equal to the search key, that is if the if condition fails for every node and temp becomes NULL, then the function returns -1 indicating that the key could not be found.

Implementation in C

#include <stdio.h>
#include <stdlib.h>
/*
Input : integer linked list , key to be searched
Ouput : Position of the key in the linked list if found, else -1
*/
struct node {
int data;
struct node *nptr; // next pointer
};

struct node *hptr = NULL; // head pointer

void insert(int pos, int x) {
struct node *temp = malloc(sizeof(struct node));
if (temp == NULL)
    printf("Insertion not possible\n");
temp->data = x; // storing the value in data field
if (pos == 1) {
    temp->nptr = hptr;
    hptr = temp;
} else {
    int i = 1;
    struct node *thptr = hptr; // temporary pointer
    while (i < pos - 1) {
    thptr = thptr->nptr; // traversing to the position of insertion
    i++;
    }
    temp->nptr = thptr->nptr;
    thptr->nptr = temp;
}
}

//Printing the content of the linked list
void print() {
struct node *temp = hptr;
printf("Linked List contains : \n");
while (temp != NULL) {
    printf("%d\n", temp->data);
    temp = temp->nptr;
}
}

//Returns the position of the key if found, else returns -1
int linearSearch(int key) {
struct node *temp = hptr;
int i = 1;
while (temp != NULL) {
    if (temp->data == key)
    return i;
    i++;
    temp = temp->nptr;
}
return -1;
}

int main() {
    insert(1, 11);
    insert(2, 13);
    insert(3, 12);
    insert(4, 14);
    insert(5, 6);
    insert(6, 10);
    print();
    printf("Position of the key is : %d\n", linearSearch(6));
    return 0;
}

Output :

Linked List contains :
11
13
12
14
6
10
Position of the key is : 5

Explanation of above C code

Let us look at the function linearSearch().

It takes the key to be searched as the input paramenter and returns the its position in the linked list. We maintain a temporary pointer temp to traverse from the node pointed by the head pointer (hptr) till the node which contains data which matches the key. We keep traversing every node, by incrementing the temp pointer (by pointing it to the next node) and check if the data in the current node is the same as the key, using an if condition.

If a match is found, we return the position, stored by the counter variable i.

If the key is not found even after temp becomes NULL, it means that we have exhausted the linked list and still could not find the key. So we return -1, indicating that the key could not be found.

Variation of the above implementation

If the input array/linked list contains duplicate elements and the key to be searched happens to occur multiple times, the above implementation only returns the first occurence of the key in the list. So, we need to tweak our linear search function to return all the positions where the key is found. We can do so by maintaining an extra array/list to store the indices of all occurences of the key and returning this array

Linear search in given array with duplicates

Implementation

#include <stdio.h>
#include <stdlib.h>
/*
Input : integer array indexed from 0, key to be searched
Ouput : Position(s) of the key in the array if found, else prints nothing
*/
int *linearSearch(int a[], int result[], int n, int key) {
  int pos = -1, ind = 0;
  for (int i = 0; i < n; ++i) {
    if (a[i] == key) {
      result[ind++] = i; // store the index of key, if found
    } else
      result[ind++] = -1; // store -1 if key not found
  }
  return result;
}

int main() {
  int a[] = {8, 12, 3, 4, 4, 7, 2, 3, 13, 17, 3};
  int n = sizeof(a) / sizeof(a[0]);
  int result[n];
  linearSearch(a, result, n, 3);
  int size = sizeof(result) / sizeof(result[0]);
  printf("Key found at position(s) : \n");
  for (int i = 0; i < size; i++) {
    if (result[i] != -1)
      printf("%d \n", result[i]);
  }

  return 0;
}

Output :

Key found at position(s) : 
2 
7 
10

Explanation of above C code

The only difference in the previous implementation of linear search in array and this is the fact that we also take care of duplicates. In order to store the positions of the multiple occurences of the key, we maintain an array result. We store the position(s) of the key if present, else we store -1 (indicating that key is not present at that index).

We store -1 because otherwise junk values would be stored and we will not be able to differentiate the actual positions from the junk values. When we store -1, we can be assured that it is not the position (since index cannot be negative).

Finally we return this result array containing -1's and the position(s) of the key. In the main function, we simply print all values of the results array except the -1's.

Linear search in given Linked List with duplicates

Implementation

#include <stdio.h>
#include <stdlib.h>
/*
Input : integer linked list , key to be searched
Ouput : Position(s) of the key in the linked list if found, else print nothing
*/
struct node {
  int data;
  struct node *nptr; // next pointer
};

struct node *hptr = NULL; // head pointer

void insert(int pos, int x) {
  struct node *temp = malloc(sizeof(struct node));
  if (temp == NULL)
    printf("Insertion not possible\n");
  temp->data = x; // storing the value in data field
  if (pos == 1) {
    temp->nptr = hptr;
    hptr = temp;
  } else {
    int i = 1;
    struct node *thptr = hptr; // temporary pointer
    while (i < pos - 1) {
      thptr = thptr->nptr; // traversing to the position of insertion
      i++;
    }
    temp->nptr = thptr->nptr;
    thptr->nptr = temp;
  }
}

void print() {
  struct node *temp = hptr;
  printf("Linked List contains : \n");
  while (temp != NULL) {
    printf("%d\n", temp->data);
    temp = temp->nptr;
  }
}
int ind;
int *linearSearch(int key, int result[]) {
  struct node *temp = hptr;
  int i = 1;
  ind = 0;
  while (temp != NULL) {
    if (temp->data == key) {
      result[ind++] = i;
    } else {
      result[ind] = -1;
      ind++;
    }
    i++;
    temp = temp->nptr;
  }
  return result;
}

int main() {
  int result[10];
  insert(1, 11);
  insert(2, 6);
  insert(3, 12);
  insert(4, 14);
  insert(5, 6);
  insert(6, 10);
  insert(7, 6);
  print();
  printf("Position(s) of the key is : \n");
  linearSearch(6, result);
  for (int i = 0; i < ind; i++) {
    if (result[i] != -1)
      printf("%d \n", result[i]);
  }
  return 0;
}

Output :

Linked List contains : 
11
6
12
14
6
10
6
Position(s) of the key is : 
2 
5 
7

Explanation of above C code

The only thing you need to know here is that we are having a global variable ind to keep track of the size of the result array (We may not need this if we know the size of linked list) . The implementation is the same as that of linear search in array with duplicates.

Application of Linear Search

• Linear search does not require the input to be sorted, unlike binary search. So Linear search can be applied in situations where the list contains random data (without any order)
• Linear search can be applied when the input list only has few elements

With this article at OpenGenus, you must have the complete idea of implementing different variants of Linear Search algorithm in C Programming Language. Enjoy.