Linear Search Algorithm: Explained in easy and simple way :)
Introduction:
Searching is the most used feature in every domain. Whether you take an example of website or mobile app or desktop app, each one of these has search feature integrated into it. Various examples include:
- Searching for a contact in contacts app.
- Making a search on YouTube for finding the video that you want to watch.
- Google search (the most common example).
Everywhere search algorithms are present. Now in the above examples that I mentioned, they all make use of advanced searching algorithms which in turn are useful in search engines like google to retrieve the results in faster and efficient way from larger datasets.
Linear search is one of the searching algorithms which is useful when we want to search in data which is unsorted/ unordered and not large amount. In general, Searching is the process of finding some particular element in the list. Also called as sequential search algorithm. It is not the most efficient algorithm but yet it is simplest of all other algorithms.
Working of Linear Search Algorithm:
- First of all, we have to traverse all the array elements using for loop.
- In each iteration of loop, we need to compare the element that we want to search with the current element in the array.
- If the search_element matches with the current_element in array, then return the index of corresponding array element.
- If the search_element does not match with the current_element in array, then simply move to the next element in array.
- If we traverse whole array and still we don’t get any match, then we can say that the element is not present in the array and hence return -1.
Code using Java:
package com.prashant.javaquestions;
public class LinearSearchDemo {
/**
* Takes an array and integer, returns index accordingly
* @param arr The 1D array of integers
* @return The index of element to find
*/
public static int linearSearch(int[] arr, int element) {
if(arr.length == 0) {
return -1;
}
for(int i = 0; i < arr.length; i++) {
if(element == arr[i]) {
return i;
}
}
return -1;
}
public static void main(String[] args) {
int arr[] = {17, 26, 27, 4, 10};
int element = 27;
int result = linearSearch(arr, element);
if(result != -1) {
System.out.println("Element found at index: " + result);
}
else {
System.out.println("Element not found...");
}
}
}
In the above output you can see that we have element = 27 to find in the array, so it is present in our array at position 3, hence it is returning the index as 2 in the output.
In the above output you can see that now we have element = 179 to find in the array, so it is not present in our array right, hence it is returning the index as -1 (which represents that element does not exist). Further in main() method, I have just added a condition to display custom message when element is not found. It is optional.
Code using JavaScript:
Create an HTML file, paste this code into it and open the HTML file in the browser.
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<style>
/* Importing Google Fonts - Roboto */
@import url('https://fonts.googleapis.com/css2?family=Roboto&display=swap');
* {
font-family: 'Roboto', sans-serif;
}
</style>
<title>Linear Search using JavaScript</title>
</head>
<body>
<script type="text/javascript">
var arr = [17, 26, 27, 4, 10];
var element = 10;
var size = arr.length;
function linearSearch(arr, element) {
if(size == 0) {
return -1;
}
for(var i = 0; i < size; i++) {
if(element == arr[i]) {
return i;
}
}
return -1;
}
var result = linearSearch(arr, element);
document.write("Array elements are: " + " ");
for(i = 0; i < size; i++) {
document.write(" " + arr[i]);
}
document.write("<br>" + "Element to search: " + " " + element);
if(result != -1) {
document.write("<br>" + "Element found at index: " + " " + result);
}
else {
document.write("<br>" + "Element not found...");
}
</script>
</body>
</html>
Time Complexity:
- Best Case: This case takes place when the element to be searched is present on the first index/ position in the array. The number of comparisons in this case would be one like when the loop will start, it will get the match in the first iteration itself and the index will be returned, hence the best case time complexity of linear search is O(1).
- Worst Case: This case takes place in 2 scenarios:
- When the element to be searched is present on last index.
- When the element to be searched is not present in the list/ array.
The number of comparisons in both the cases would be N like let’s say suppose we have array of 10 elements, then the loop will start and it will do comparisons with all the elements. Now in this case of our example, it will do 10 comparisons but in place of 10 we don’t know that how many elements we would be getting like there can be any number of elements right, so we represent it as “N” elements. Hence the worst case time complexity of linear search is O(N).
3. Average Case: This case takes place in 2 scenarios:
- When the element to be searched is present at multiple indexes.
- When the element to be searched is not present in the list/ array.
In this case also the time complexity would be O(N). If you want to understand how it is calculated mathematically, you can view it by clicking here.
Space Complexity:
The space complexity of the linear search algorithm is O(1), which is constant space complexity.
The reason for this is that the algorithm does not use any additional space that scales with the size of the input. Regardless of the size of the input array, the algorithm only requires a fixed amount of space for the integer variables used for iteration and comparison, as well as the array itself. Hence, the algorithm’s space complexity remains constant and does not change/ increase with the input size.
Applications/ Real-life scenarios:
- Simple Databases: In small or unsorted databases or lists, linear search may be used to find specific records or entries. For example, a contact list on a mobile or a small inventory list may use linear search to locate specific items.
- User Interfaces: In user interfaces or front-end applications, linear search is often used for basic search functionalities. For example, when searching for a specific item in a drop-down list or a simple search bar, a linear search algorithm can be used to find and display the matching items.
- Small-scale Data Processing: In scenarios where the dataset is limited and efficiency is not a critical factor, linear search may be used. For example, searching for a specific word in a document or a simple text file can be implemented using a linear search algorithm.
- Educational Purposes: Linear search algorithms are often used to introduce students to the concept of searching in programming. They can be used in colleges to demonstrate the basics of searching and algorithmic complexity.
References:
So that was all about linear search algorithm in simple and easy way.
