Get this book -> Problems on Array: For Interviews and Competitive Programming

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

## Question 1

#### How many comparisons are made to find the key where input array is [12, 3, 5, 11, 6] and the key is 7 ?

## Question 2

#### Why is linear search technique is not used often ?

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