Linear Search Algorithm
FREE
Searching is a method to find some relevant information in a data set. In computer programming, searching is usually referred to as finding a particular element in a data structure. Linear search algorithm is a straightforward search algorithm. This type of search performs a sequential search on all items individually. In this article, we will be learning about Linear Search Algorithm.
How Linear Search Algorithm Works?
Linear search is an algorithm which is used to find a target value within an array of elements. Here's how it works:
- Start from the beginning of the array (i = 0) and traverse each element sequentially.
- If the current element equals the target value (arr[i] == K), return the index i.
- If the end of the array is reached without finding the target value (i >= n), return -1 to indicate that the value was not found.
- If the current element doesn't match with the target value, move to the next element (i++) and repeat the process.
Linear Search Algorithm: Finding a Number in an Array
Linear search is a simple algorithm which is used to find a target value within an array of elements. Imagine you have an array of integers like this:
And you want to find the number 9 within this array.
- Start from the beginning of the array (i = 0) and traverse each element sequentially.
- If the current element equals the target value (arr[i] == 9), return the index i.
- If the end of the array is reached without finding the target value (i >= n), return -1 to indicate that the value was not found.
- If the current element does not match the target value, and then it will move to the next element (i++) and repeat the process.
Implementation of Linear Search Algorithm
Transform Your Career
Choose from our industry-leading programs designed for career success
Modern Software and AI Engineering Program
Master full-stack development with AI integration
+1000 moreModern Data Science and ML with specialisation in AI
Advanced data science techniques with AI specialization
+1000 moreAdvanced AIML with Specialisation in Agentic AI
Deep dive into AIML with focus on Agentic systems
+1000 moreDevOps, Cloud & AI Platform Engineering
Build and manage AI-powered cloud infrastructure
+1000 moreAI Engineering Advanced Certification by IIT-Roorkee
Premier AI engineering certification from IIT-Roorkee
Below is a Simple Implementation of Linear Search in Java.
Scaler Placement Report and Statistics
Scaler learners achieved 2.5x salary growth with average post-Scaler CTC reaching ₹23L.
Below is a Simple Implementation of Linear Search in Python.
Below is a Simple Implementation of Linear Search in C++.
Output
Turn Learning into Career Growth
Complexity Analysis of Liner Search Algorithm
Time Complexity of Linear Search Algorithm
Best case: In the best case, we might find K in the first iteration only, i.e. it is the first element of the array, so it is O(1).
Worst case: In the worst case, **we might find K in the last iteration or not find K in the array.
On average, it might be present around the middle of the array, so its complexity is O(n/2) ~ O(n).
Space Complexity of Linear Search Algorithm
As it is evident, we are not using any significant extra memory in linear search. So the space complexity is constant, i.e. O(1).
Advantage of Liner Search Algorithm
The advantages of the Linear Search Algorithm include:
- Simplicity: Linear search is straightforward to implement, making it suitable for beginners and for situations where simplicity is preferred over efficiency.
- Applicability to Unsorted Data: Unlike other search algorithms like binary search, which require sorting data, linear search can be applied to both sorted and unsorted arrays.
- No Preprocessing Required: Linear search requires no data preprocessing before searching, making it efficient for searching in dynamic or frequently changing data sets.
- Ease of Understanding: The algorithm is straightforward, making it accessible for those new to programming or algorithms.
Drawbacks of Liner Search Algorithm
The drawbacks of the Linear Search Algorithm include:
- For large data sets, linear search may need to be more efficient than other search algorithms with lower time complexities.
- Linear search traverses the entire array even if the target element is found early in the search process. This can result in unnecessary comparisons and wasted computational resources.
- The efficiency of linear search depends on the distribution of data. Linear search may need more comparisons on average if the target element is towards the end of the array rather than evenly distributed throughout it.
When to use Linear Search Algorithm?
Linear search in Data Structure is widely used, and these are the following scenarios:
- Linear search works fine when we will be using small data sets.
- Linear search within Data Structures finds everyday use within singly-linked lists.
- Linear search is used when frequent updates are needed.
Scaler Placement Report and Statistics
Scaler learners achieved 2.5x salary growth with average post-Scaler CTC reaching ₹23L.
Conclusion
- Linear search is a simple search-based algorithm that sequentially scans through all elements in a data collection to find a target element.
- In the worst and average cases, the time complexity of the Linear search algorithm is O(n).
- Advantages of linear search include simplicity, applicability to unsorted data, no preprocessing required, and ease of understanding.
- Drawbacks of linear search include inefficiency for large data sets, unnecessary comparisons, and dependence on data distribution.
Stay tuned for the articles on Binary Search and Interpolation Search.
Thanks for reading. May the code be with you 🙂
Google
Amazon
Microsoft
Flipkart
Adobe1200+ more