What Is Linear Search Program in Data Structure?
In the world of computer science and data structures, the linear search algorithm is one of the simplest and most fundamental algorithms. It is used to find a specific element within a collection or an array by sequentially checking each element until a match is found or the entire collection has been traversed.
The linear search algorithm works by starting at the beginning of the collection and comparing each element with the Target value. If a match is found, the algorithm returns the index of that element.
However, if no match is found after checking every element, it returns a predefined value like -1 to indicate that the Target value does not exist in the collection.
Implementing Linear Search in C++
To understand how linear search works, let’s take a look at a simple C++ program that implements this algorithm:
#include <iostream>
using namespace std;
int linearSearch(int arr[], int n, int Target) {
for (int i = 0; i < n; i++) {
if (arr[i] == Target) {
return i;
}
}
return -1;
}
int main() {
int arr[] = {10, 25, 30, 45, 50};
int n = sizeof(arr) / sizeof(arr[0]);
int Target = 30;
int result = linearSearch(arr, n, Target);
if (result == -1) {
cout << "Element not found";
} else {
cout << "Element found at index " << result;
}
return 0;
}
In this example program, we define a function called linearSearch which takes an array arr, its size n, and the Target value to search for. The function iterates through each element of the array using a for loop.
If a match is found, it returns the index of that element. Otherwise, it returns -1.
In the main function, we define an array of integers arr and initialize it with some values. We also specify the Target value to search for, which in this case is 30.
The result of calling the linearSearch function is stored in the variable result. Finally, we check if the result is -1 and print either "Element not found" or "Element found at index X", where X is the index of the Target element.
Time Complexity Analysis
The time complexity of linear search depends on the size of the collection. In the worst-case scenario, where the Target element is not present or located at the end of the collection, linear search needs to check every element one by one.
Therefore, its time complexity is O(n), where n is the number of elements in the collection.
Conclusion
Linear search is a simple yet essential algorithm in computer science and data structures. It provides a basic approach to find an element within a collection by checking each element sequentially until a match is found or all elements have been checked.
While it may not be efficient for large collections, it serves as a fundamental building block for more advanced searching algorithms.