Linear Search Algorithm — Implementation in Java

Linear search using Java

This blog is intended to explain about the Linear Search Algorithm and its working with an implementation using Java.

So, What is a Search algorithm?
A search algorithm is an algorithm used to find a piece of information stored within a dataset. There are different types of search algorithms that are classified based on the efficiency and type of information being searched. The most commonly used search algorithms are Linear, Binary, interpolation, jump etc… In this blog, I will concentrate on the Linear Search algorithm with a simple implementation using Java.

Table of Content

1. What is a Linear Search Algorithm?
2. Implementation of Linear Search Algorithm using Java.
3. Complexity Analysis.
4. Pros and Cons of using a Linear Search Algorithm.
5. Takeaway.

1. What is a Linear Search Algorithm?

The Linear Search algorithm is the simplest search algorithm that uses a sequential method to find an element from a dataset. The Algorithm iterates over all the elements in the dataset until the search element is found.

To explain Linear search consider a dataset with an array of numbers. The objective is to find element 2 from the dataset.

Linear search works by comparing all the elements in a dataset. So initially the algorithm compares the value at the zeroth index of the dataset with the Search element. Since 1 is not equal to 2, the loop breaks and compares the search element with the value at index 1.

Even at the first Index the search fails since the value at index 1 is 3. So again the same process continues.

In the second index, the search condition matches since the value at index two is 2.

2. Implementation of Linear Search Algorithm using Java.

To implement the Linear search algorithm let’s take the same array we used above ([1,3,2,6,5,4,9,8,7] ). Let the array be stored in the variable inputList and let the element to be searched be 6 which is stored in the variable searchElement .

  int inputList[] = { 1,3,2,6,5,4,9,8,7 };
  int searchElement = 6;

Now let’s create a function called linearSearch which accepts two inputs. One will be the inputList and the other will be the searchElement . Based on these two inputs this function will return the position of the search element. If the search Element is not found, the function will just return -1.

Now let’s deep dive into the logic used inside the function. Using a for loop the function iterates inputList and compares each and every element of the array with the searchElement . The loop continues until the searchElement is found in the array. When the search element is found, the loop breaks and the index is returned.

 public static int linearSearch(int inputList[], int searchElement) {
  int position = -1;
  for (int i = 0; i < inputList.length; i += 1) {
   int _itr = inputList[i];
   if (_itr == searchElement) {
    position = i;
    break;
   }
  }
  return position;
 }

So now, we can directly call the function and pass the necessary variables to it. -1 will indicate that the search element is not found. Since the index values of Java start from zero we will be adding 1 ( position + 1 ) to the variable position.

int position = LinearSearch.linearSearch(inputList, searchElement);

if (position != -1) {
   System.out.println("Search Element found at position: "+ (position + 1));
  } else {
   System.out.println("Search Element not found");
}

Wrapping up altogether.

class LinearSearch {
 
 public static int linearSearch(int inputList[], int searchElement){
  int position = -1;
  for (int i = 0; i < inputList.length; i += 1) {
   int _itr = inputList[i];
   if (_itr == searchElement) {
    position = i;
    break;
   }
  }
  return position;
 }
public static void main(String args[]) {
  int inputList[] = { 1,3,2,6,5,4,9,8,7 };
  int searchElement = 6;
  int position = LinearSearch.linearSearch(inputList, searchElement);
if (position != -1) {
   System.out.println("Search Element found at position: "+ (position + 1));
  } else {
   System.out.println("Search Element not found");
  }
 }
}

3. Complexity Analysis.

Taking about complexity, let’s look into both time and space complexity.

a) Time Complexity

The time complexity of a Linear search algorithm is measured using the number of comparisons made.

Best case scenario: Best case scenario occurs when the search element is in the first position of the dataset. In this case, the algorithm need not iterate over the entire dataset. It needs only one comparison. So the best-case time complexity of a Linear search algorithm is O(1).

Average case scenario: In the Average case scenario, the search element will be somewhere in the middle of the dataset. Therefore in the average case scenario, the complexity will be O(n).

Worst case scenario: The worst case scenario occurs when the search element is at the tail of the dataset or not present at all. In this case, the algorithm has to search over the entire dataset until the search element is found. Hence the time complexity of the worst-case scenario is also O(n).

The ‘O’ represents the rate at which the algorithm’s time complexity increases. The ’n’ indicates that the time complexity of the algorithm is directly proportional to the size of the input. So if the input size increases, the time also increases.

b) Space Complexity

The space complexity of an algorithm is measured by the factors such as the memory/space utilization required by the algorithm to execute.

The space complexity of a Linear Search is O(1) because it does not require any additional space to execute the algorithm. Very few variables could be used to keep track of the current element regardless of the dataset size.

4. Pros and Cons of using Linear Search.

Pros of Linear Search
a) Ease of Implementation — Linear search is the easiest and the most straightforward algorithm. The implementation is to iterate and search for an element in a dataset until the element is found.

b) Applicable for unsorted data — Unlike other search algorithms Linear search does not require pre-processing. It works fine with both sorted and unsorted datasets. It doesn’t require any specific order or structure, making it versatile for various data types and scenarios.

c) Best for best case scenario — When the search element is at the first position, the Linear algorithm is the best algorithm since the resultant is found at the first iteration itself.

d) Less space complexity — Linear search does not require high space to get executed.

Cons of Linear Search
a) Worst-case Time complexity — The linear search algorithm has a time complexity of O(n). When the target element is at the end or not present at all, the algorithm needs to traverse the entire dataset. As a result, the linear search will be inefficient for large datasets, especially when compared to more optimized search algorithms.

b) Limited Scalability — Due to its linear nature, the time taken by linear search grows linearly with the input size. This can be a limitation when dealing with significantly large datasets, as the search time may become impractical or unacceptably slow.

c) Bad Performance for Sorted Data — Linear search doesn’t take advantage of sorted datasets. It cannot exploit the sorted order to skip unnecessary comparisons, which makes it less efficient than binary search or other algorithms designed for sorted data.

5. TakeAway.

Thought Linear search is easy to learn and implement it is good only for the best-case scenario. Since we have to iterate over all the elements of the dataset in order to find the search element, the Linear search will not be suitable for worst-case scenarios and cases where the search element is itself not found in the dataset. Some of the disadvantages of Linear Search can be solved using the Binary Search algorithm. In the next blog let’s discuss the working of the Binary Search Algorithm in detail.

Please find the code on GitHub

Medium-Data-Structures/linear-search at master · sjlouji/Medium-Data-Structures