Linear Search Algorithm

Video Tutorial
FREE
Linear Search Algorithm thumbnail
This video belongs to
Java Course - Mastering the Fundamentals
12 modules
Certificate

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 learn about Linear Search Algorithm.

How Linear Search Algorithm Works?

Let’s say we’re trying to search for a number, K, in an array containing random integers.

Let’s say the array is

5 3 12 9 45 1 22

And the element we’re searching for, K = 9

What is the most intuitive way to do it?

If you’re thinking of starting from the beginning of the array and checking whether the element is equal to K or not until you either find K or reach the end, congratulations, you’ve just defined Linear Search yourself 😛

Let’s define it more clearly.

In Linear search, we traverse each array element, one by one, and check whether it equals the element to be searched. It is also called sequential search because it checks all the elements sequentially.

If you find an element equal to K, we can say that K is present in the array. If we reach the end and still haven’t found K, we can confirm that K is not present in the array. Let’s try to use linear search for the above input.

5 3 12 9 45 1 22 – Found K = 9 at index 3

Working of linear search algorithm

As you can see, we found K in the fourth comparison.

Why do we need to start from the beginning, not the end or middle? You’re right; we can do either of those. But think about it, does it help? The answer is: not really.

If you try to search for 9 from the end rather than the beginning, you’ll find it in the fourth iteration only.

5 3 12 9 45 1 22 – Found K = 9 at index 3

Working of linear search algorithm 1

To simplify, if K is present in the first half of the array, it’ll be better to start from the beginning. On the other hand, if it’s present in the latter half, it’s better to start from the end.

But think about it: do we know where the element might be present in a wholly randomised array? Or even the fact that whether it is present or not? We don’t, right? That’s what we’re using linear search for.

It is quite possible that if you start from the beginning, K might be the last element of the array, and if you start from the end, it might be the first one.

So, if we consider the worst case possibility, we will search only the complete array every time. Hence, it hardly matters where we start the search.

Below is the algorithm for Linear Search.

  1. Initialise i = 0 and n = size of array
  2. if i >= n, we have reached the end of the array and could not find K. We return -1 to signify that the element K was not found.
  3. if arr [ i ] == K, it means that we have found an element equal to K at index 'i’ and do not need to search the remaining array. We return the index 'i’ directly from here, which is the index at which K was found in this array
  4. else arr [ i ] != K, which means the current element is not equal to K, and we will repeat step 2 with the next array element by incrementing i, i.e. ++i.

Implementation of Linear Search Algorithm

Below is a simple implementation of Linear Search in Java.

Output:

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:

  1. Simplicity: Linear search is straightforward to implement, making it suitable for beginners and for situations where simplicity is preferred over efficiency.
  2. 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.
  3. No Preprocessing Required: Linear search requires no data preprocessing before searching, making it efficient for searching in dynamic or frequently changing data sets.
  4. 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:

  1. For large data sets, linear search may need to be more efficient than other search algorithms with lower time complexities.
  2. 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.
  3. 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:

  • Small Data Sets: Linear search works well with small data sets with relatively low elements. In such cases, the overhead of implementing more complex search algorithms may not be justified.
  • Unsorted Data: Linear search is effective when the data is unsorted, or the order of elements is not essential. It sequentially checks each element until a match is found, regardless of the arrangement of elements.
  • Singly Linked Lists: Linear search in Data Structure is commonly used in single lists where direct access to elements is impossible. It traverses the list one node at a time, making it a suitable choice for searching through linked structures.
  • Infrequent Searches: If searches are infrequent or the list needs to be frequently updated, linear search can be a straightforward and sufficient solution.
  • Educational Purposes: Linear search is often used as an introductory algorithm in programming and computer science courses to illustrate basic search concepts before moving on to more advanced algorithms.

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, 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 🙂