Linear search is a fundamental searching algorithm used in programming to find the presence of an element in an array. The algorithm works by sequentially checking each element of the array until the desired element is found or the end of the array is reached. This article will guide you through the implementation of a C++ program to perform a linear search, providing multiple examples to demonstrate various solutions and their outputs.
Prerequisites
Before diving into the implementation, you should have:
- Basic understanding of C++ programming.
- Familiarity with arrays and loops.
With these prerequisites, you will be able to grasp the concepts and code implementations discussed here.
1. Linear Search Algorithm
1.1 Basic Linear Search
Let’s start with a basic implementation of the linear search algorithm.
#include <iostream>
int linearSearch(int arr[], int n, int x) {
for (int i = 0; i < n; i++) {
if (arr[i] == x) {
return i; // Return the index of the found element
}
}
return -1; // Return -1 if the element is not found
}
int main() {
int arr[] = {2, 3, 4, 10, 40};
int n = sizeof(arr) / sizeof(arr[0]);
int x = 10;
int result = linearSearch(arr, n, x);
if (result != -1) {
std::cout << "Element found at index " << result << std::endl;
} else {
std::cout << "Element not found in the array" << std::endl;
}
return 0;
}
1.2 Output Explanation
In this example, the input array is {2, 3, 4, 10, 40} and the element to be searched is 10. The program performs a linear search and finds the element at index 3.
Element found at index 3
1.3 Time Complexity
The time complexity of the linear search algorithm is O(n)O(n)O(n) where nnn is the number of elements in the array. This is because in the worst case, the algorithm has to check each element once.
2. Enhancing Linear Search
2.1 Sentinel Linear Search
A slight optimization of the linear search can be achieved by using a sentinel. This reduces the number of comparisons in the search process.
#include <iostream>
int sentinelLinearSearch(int arr[], int n, int x) {
int last = arr[n - 1];
arr[n - 1] = x; // Set the last element as the target element
int i = 0;
while (arr[i] != x) {
i++;
}
arr[n - 1] = last; // Restore the last element
if (i < n - 1 || arr[n - 1] == x) {
return i; // Return the index of the found element
}
return -1; // Return -1 if the element is not found
}
int main() {
int arr[] = {2, 3, 4, 10, 40};
int n = sizeof(arr) / sizeof(arr[0]);
int x = 10;
int result = sentinelLinearSearch(arr, n, x);
if (result != -1) {
std::cout << "Element found at index " << result << std::endl;
} else {
std::cout << "Element not found in the array" << std::endl;
}
return 0;
}
2.2 Output Explanation
In this example, the input array is {2, 3, 4, 10, 40} and the element to be searched is 10. The program performs a sentinel linear search and finds the element at index 3.
Element found at index 3
2.3 Time Complexity
The time complexity of the sentinel linear search algorithm remains O(n)O(n)O(n). However, it can be more efficient in terms of the number of comparisons made during the search process.
3. Handling Edge Cases
3.1 Element Not Present
Let’s handle the edge case where the element to be searched is not present in the array.
int main() {
int arr[] = {2, 3, 4, 10, 40};
int n = sizeof(arr) / sizeof(arr[0]);
int x = 5;
int result = linearSearch(arr, n, x);
if (result != -1) {
std::cout << "Element found at index " << result << std::endl;
} else {
std::cout << "Element not found in the array" << std::endl;
}
return 0;
}
3.2 Output Explanation
In this example, the input array is {2, 3, 4, 10, 40} and the element to be searched is 5. The program performs a linear search and does not find the element.
Element not found in the array
4. Using C++ Standard Library
4.1 Using std::find
We can also utilize the C++ Standard Library function std::find from the <algorithm> header to simplify the process.
#include <iostream>
#include <algorithm>
int main() {
int arr[] = {2, 3, 4, 10, 40};
int n = sizeof(arr) / sizeof(arr[0]);
int x = 10;
auto it = std::find(arr, arr + n, x);
if (it != arr + n) {
std::cout << "Element found at index " << it - arr << std::endl;
} else {
std::cout << "Element not found in the array" << std::endl;
}
return 0;
}
4.2 Output Explanation
In this example, the input array is {2, 3, 4, 10, 40} and the element to be searched is 10. The program uses std::find to locate the element and finds it at index 3.
Element found at index 3
Conclusion
A C++ program to implement a linear search can be written in various ways, from a basic linear search to a sentinel linear search. Utilizing the C++ Standard Library’s std::find function can further simplify the implementation.