Linear search is a simple yet effective algorithm used to search for a particular element or value in an array or list. It is one of the most fundamental algorithms used in data structures and algorithms with C++. In this article, we will discuss the basic concept of linear search, its time and space complexities, and a C++ implementation of the algorithm. We will also explore a few coding exercises at the end to test your understanding of linear search.

## What is Linear Search?

Linear search is a technique of searching through a sequential set of elements or values until the desired element is found. It sequentially checks each element of the given array until a match is found or the end of the array is reached. As the name suggests, the elements are searched one by one in a linear fashion. The time required for a linear search depends on the size of the array and the location of the element.

Linear search is also known as a sequential search or brute-force search as it involves searching through every element until the desired element is found. This algorithm is simple to implement and does not require any pre-processing of the data. It is most suitable for smaller data sets as it has a time complexity of O(n).

## Time Complexity of Linear Search

The time complexity of linear search is O(n), where n is the number of elements in the array. This means that the time required to search for an element increases linearly with the number of elements in the array.

The best-case time complexity of linear search is O(1) when the element is found at the beginning of the array. The worst-case time complexity is O(n) when the element is found at the end of the array. The average time complexity is also O(n).

## Space Complexity of Linear Search

The space complexity of linear search is O(1). This means that the algorithm requires a constant amount of space irrespective of the size of the array.

## C++ Implementation of Linear Search

Let’s look at a simple implementation of linear search in C++. The following code searches for a given element in an array and returns its index if found; otherwise, it returns -1.

```
#include <iostream>
using namespace std;
int linearSearch(int arr[], int n, int x)
{
int i;
for (i = 0; i < n; i++)
if (arr[i] == x)
return i;
return -1;
}
int main()
{
int arr[] = { 1, 10, 30, 15 };
int x = 30;
int n = sizeof(arr) / sizeof(arr[0]);
int result = linearSearch(arr, n, x);
if (result == -1)
cout << "Element is not present in array" << endl;
else
cout << "Element is present at index " << result << endl;
return 0;
}
```

In the above code, we have declared a function linearSearch() which takes an array arr[], the size of the array n, and the element x to be searched. Then, we traverse the array from index 0 to n-1 and check if the element is equal to the desired element. If the element is found, the index is returned; otherwise, -1 is returned.

In the main() function, we have declared an array arr[] and an element x to be searched. Then, we call the linearSearch() function and pass the array, size, and element as parameters. This function returns the index at which the element is found, or -1 if it is not found.

## Conclusion

In this article, we discussed linear search, its time and space complexities, and its C++ implementation. We also looked at a few coding exercises to test your understanding of linear search. Linear search is a simple algorithm and is best suited for small data sets. It has a time complexity of O(n) and a space complexity of O(1).

Linear search is one of the fundamental algorithms used in data structures and algorithms with C++. It is important to understand the basics of linear search, its implementation, and its complexities before moving on to more complex algorithms.

## Exercises

#### Write a function to search for an element in a linked list using linear search.

```
#include <iostream>
using namespace std;
struct Node
{
int data;
struct Node* next;
};
int linearSearch(struct Node* head, int x)
{
struct Node* current = head;
int index = 0;
while (current != NULL)
{
if (current->data == x)
return index;
current = current->next;
index++;
}
return -1;
}
int main()
{
struct Node* head = NULL;
head = new Node;
head->data = 10;
head->next = new Node;
head->next->data = 20;
head->next->next = new Node;
head->next->next->data = 30;
head->next->next->next = NULL;
int x = 20;
int result = linearSearch(head, x);
if (result == -1)
cout << "Element is not present in the list" << endl;
else
cout << "Element is present at index " << result << endl;
return 0;
}
```

#### Write a program to search for an element in a 2D array using linear search.

```
#include <iostream>
using namespace std;
#define R 4
#define C 4
int linearSearch(int arr[R][C], int x)
{
int i, j;
for (i = 0; i < R; i++)
for (j = 0; j < C; j++)
if (arr[i][j] == x)
return 1;
return 0;
}
int main()
{
int arr[R][C] = { { 10, 20, 30, 40 },
{ 15, 25, 35, 45 },
{ 27, 29, 37, 48 },
{ 32, 33, 39, 50 } };
int x = 29;
int result = linearSearch(arr, x);
if (result == 0)
cout << "Element is not present in the array" << endl;
else
cout << "Element is present in the array" << endl;
return 0;
}
```

#### Write a program to search for an element in a BST using linear search.

```
#include <iostream>
using namespace std;
struct Node
{
int data;
struct Node* left, *right;
};
int linearSearch(struct Node* root, int x)
{
if (root == NULL)
return 0;
if (root->data == x)
return 1;
if (root->data > x)
return linearSearch(root->left, x);
return linearSearch(root->right, x);
}
int main()
{
struct Node* root = NULL;
root = new Node;
root->data = 20;
root->left = new Node;
root->left->data = 8;
root->right = new Node;
root->right->data = 22;
root->left->left = new Node;
root->left->left->data = 4;
root->left->right = new Node;
root->left->right->data = 12;
int x = 22;
int result = linearSearch(root, x);
if (result == 0)
cout << "Element is not present in the tree" << endl;
else
cout << "Element is present in the tree" << endl;
return 0;
}
```

#### Write a program to search for an element in a hash table using linear search.

```
#include <iostream>
#include <list>
using namespace std;
class HashTable
{
int size;
list<int>* table;
public:
HashTable(int size)
{
this->size = size;
table = new list<int>[size];
}
void insertItem(int key)
{
int index = hashFunction(key);
table[index].push_back(key);
}
int linearSearch(int key)
{
int index = hashFunction(key);
list<int>::iterator i;
for (i = table[index].begin(); i != table[index].end(); i++)
if (*i == key)
return 1;
return 0;
}
private:
int hashFunction(int key)
{
return (key % size);
}
};
int main()
{
HashTable ht(7);
ht.insertItem(18);
ht.insertItem(25);
ht.insertItem(42);
ht.insertItem(17);
int x = 18;
int result = ht.linearSearch(x);
if (result == 0)
cout << "Element is not present in the hash table" << endl;
else
cout << "Element is present in the hash table" << endl;
return 0;
}
```

#### Write a program to search for an element in a linked list using linear search in a recursive manner.

```
#include <iostream>
using namespace std;
struct Node
{
int data;
struct Node* next;
};
int linearSearchRecursive(struct Node* head, int x, int index)
{
if (head == NULL)
return -1;
if (head->data == x)
return index;
return linearSearchRecursive(head->next, x, index+1);
}
int main()
{
struct Node* head = NULL;
head = new Node;
head->data = 10;
head->next = new Node;
head->next->data = 20;
head->next->next = new Node;
head->next->next->data = 30;
head->next->next->next = NULL;
int x = 20;
int result = linearSearchRecursive(head, x, 0);
if (result == -1)
cout << "Element is not present in the list" << endl;
else
cout << "Element is present at index " << result << endl;
return 0;
}
```