Linear Search in C++

Yasin Cakal

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; 
}

Data Structures and Algorithms with C++

Participants 673