What is Linear Search?
This process involves locating a specific element within a dataset, commonly referred to as Linear Search or Sequential Search. The dataset can be composed of an array, list, or similar linear data structures. During the linear search process, each element is sequentially examined until the desired element is found or the end of the dataset is reached. Upon finding the element, the algorithm provides its position, otherwise indicating to the user that the element is not present in the dataset.
Understanding the Working of the Linear Search Algorithm?
The steps listed below can help you understand the linear search algorithm:
- Start with the collection's initial element, which is often where you should begin.
- A comparison between the present element and the sought-after target element is made.
- Return the index (position) of the current element if the target element and the current element are the same.
- Continue on to the following element in the collection if the element under examination does not satisfy the conditions.
- Repeat steps 2-4 until you have identified the target element or have finished the collection.
- Return a signal (like -1) to show that the element is absent if you reach the collection's conclusion without discovering the desired element.
- 'arr' stands for the collection (array or list) you wish to do a search on.
- The element you wish to find in the collection is referred to as the "target."
- The 'for' loop iterates through each component of the collection.
- If the current element and the target element are equal, the loop is checked.
- The element's index is returned if a match is made.
- It returns -1 to show that the element is not present in the collection if the loop ends without finding the target element.
Pseudocode of the Linear Search Algorithm
function linearSearch(arr, target):
for i from 0 to length(arr) - 1 do:
if arr[i] equals target then:
return i // Element found, return its index
end for
return -1 // Element not found
Code implementation of Linear Search Algorithm in C Programming Language
Let's now examine this C programming code snippet that demonstrates the Linear Search Algorithm:
Example Code:
#include <stdio.h>
// Function to perform linear search
int linearSearch(int arr[], int n, int target) {
for (int i = 0; i < n; i++) {
if (arr[i] == target) {
return i; // Element found, return its index
}
}
return -1; // Element not found
}
int main() {
int arr[] = {12, 45, 23, 67, 9, 56, 32};
int n = sizeof(arr) / sizeof(arr[0]);
int target = 56;
int result = linearSearch(arr, n, target);
if (result != -1) {
printf("Element found at index %d\n", result);
} else {
printf("Element not found in the array\n");
}
return 0;
}
Explanation:
In the code:
- The 'linearSearch' has three iputs: the array you want to search, the number of array elements('n'), and the element you want to locate('arr', 'target').
- We utilize the 'for' loop within the 'linear search' function to cycle through the elements of the array.
- If the match is found, we return the index of the matching element after comparing each element with the target' element.
- We return -1 to indicate that the target element is not present in the array if the loop ends without finding it.
- The 'linearSearch' function is used in the main function to show how to find an element in an array. In this example, we will look in the 'arr' array for element 56 and print the result.
Output:
Element found at index 5
Time complexity
The quantity of elements within the collection under scrutiny, represented as "n," dictates the time complexity of the linear search algorithm, which is O(n). In situations where every element needs to be examined, the algorithm's processing time increases proportionally with the input data's magnitude.
Space Complexity
The linear search algorithm has a space complexity of O(1) as it requires a fixed amount of extra storage space, irrespective of the size of the input.
Some Advantages of the Linear Search Algorithm in C
- Simplicity: One of the easiest searching algorithms to comprehend and use is linear search. It doesn't call for intricate data structures or specialized skills, and it uses simple reasoning.
- Universal Applicability: Any collection of data, including those in an array, list, or other linear data structure, may be searched using linear methods. It is a useful tool in a variety of programming settings because of its adaptability.
- Works on Unsorted Data: Contrary to certain other search techniques like binary search, which favour sorted data, linear search is equally effective with both sorted and unsorted data. It doesn't assume anything regarding the sequence of the data.
- No Preprocessing Request: The data don't need to be preprocessed before using linear search. Without doing any more actions, you may apply it straight to the dataset. In circumstances where data regularly changes, this may be useful.
- Low Memory Overhead: A linear search takes up very little memory. It is useful for contexts with little memory since it normally only utilizes a small number of variables to maintain track of the current position.
- Suitable for Small Data sets: The performance difference between linear search and more complicated methods is minimal when the dataset is small. The simplicity and convenience of use of linear search can be helpful in these circumstances.
- Ease of Debugging: It is simple to test and troubleshoot linear searches. In the debugging stage, linear search may be a rapid and efficient approach to quickly confirm the existence of an element in a dataset when working with complicated data structures or algorithms.
- Inefficiency of Large Datasets: As the dataset becomes bigger, linear search becomes incredibly inefficient. Because of its O(n) time complexity, searching for an element becomes more time-consuming as there are more items. Large datasets may have slow performance as a result of this.
- Not Suitable for Real-time Systems: The linear search technique may not be appropriate in real-time systems or applications where low latency is essential due to its possible sluggish execution on huge datasets.
- Limited Use cases: Finding a single instance of an element is the main purpose of linear search. Other algorithms, such as binary search or hash tables, are more effective options if you need to discover many occurrences or carry out more complicated searches.
- No Early Termination: If the dataset is ordered in a certain way or if it is known that the target element cannot exist in certain regions of the dataset, linear search does not end early. It may be less effective than algorithms that benefit from such knowledge due to this lack of early termination.
- Doesn't Utilize Sorted Data: Sorted data are not utilized by linear search. With a temporal complexity of O(log n), alternative algorithms like binary search can operate much more quickly if your dataset is sorted.
- Not Suitable for Complex Data Structures: Simple linear data structures like arrays and lists are ideal candidates for linear search. More specialized algorithms are needed for complicated data structures like trees or graphs.
- Performance Variability: Depending on where the target element is located in the dataset, linear search performance may change. The approach is effective if the element is located early in the search; however, if it is discovered later in the process or not at all, the algorithm becomes ineffective.
Some Disadvantages of the Linear Search Algorithm in C
Use Cases
Despite not being the most effective search method, linear search has its applications. Here are some circumstances in which linear search may be a good choice:
- Small Datasets: The performance difference between linear search and more complicated methods is minimal when working with small datasets. The simplicity of linear search may be advantageous in some circumstances.
- Unsorted Data: Given that it does not depend on a particular element's arrangement, linear search is effective on unsorted data. When you can't ensure that the data will always be sorted, this can be helpful.
- Testing and Debugging: During debugging or testing phases, linear search may be used as a quick and simple method to confirm whether a given element exists in a dataset.
The Conclusion
A basic and straightforward technique for finding an item within a dataset is the linear search algorithm. This method is particularly beneficial for unsorted and small datasets, although its efficiency diminishes as the dataset grows larger. While it may not be the most efficient search method, grasping the concept of linear search is essential for all programmers and serves as a valuable entry point into the realm of algorithms.