Linear Search Algorithm

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:

1. Start from the beginning of the array (i = 0) and traverse each element sequentially.
2. If the current element equals the target value (arr[i] == K), return the index i.
3. 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.
4. 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.

1. Start from the beginning of the array (i = 0) and traverse each element sequentially.
2. If the current element equals the target value (arr[i] == 9), return the index i.
3. 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.
4. 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

Below is a Simple Implementation of Linear Search in Java.

Below is a Simple Implementation of Linear Search in Python.

Below is a Simple Implementation of Linear Search in C++.

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:

• 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.