ELI5: Linear Search Algorithms 🕵️♀️
Let’s talk about algorithms. Today, I’ll breakdown (like you’re 5 years old) what a linear search algorithm is, how to implement it in JavaScript, and when we use it. Ready? Let’s go!
What is the Linear Search Algorithm? ➡️➡️➡️➡️
Simply put, the linear search algorithm is a way to find a particular item in a specific list/array. We’re dealing with two things for this algorithm: 1) the list/array containing many items; and, 2) the specific item we’re looking for. Okay, the linear search algorithm provides a framework to find a specific item we’re looking for in a given array of data.
Characteristics of the Linear Search Algorithm 📝
- the simplest algorithm
- uses a for loop
- best used to search small sets of data
- best when looking for one element
The Code: Implementing Linear Search ⌨️
What does the linear search algorithm look like written in JavaScript? I’ve written it out for you below:
function linearSearchAlgo(array, itemToSearchFor){
for(let i = 0; i < array.length; i++){
if(array[i] === itemToSearchFor) return i;
}
return -1;
}Wow, this algorithm is short and to the point. What’s actually happening? Our function takes in two parameters: array and itemToSearchFor. The body of our function is a simple for loop. This means we’ll be starting from the beginning position of the array, index 0, and looping through each index position until we find the item we’re looking for or we loop through every index position and don’t find what we’re looking for.
Inside the for loop we compare the current item with itemToSearchFor. If they are a match, we return the index position of the current loop. Else, if they never match we return -1 (or we could return null, or “Sorry, we can’t find the item you’re looking for”, or false, or really you can return anything you want to indicate the search failed).
When do we use Linear Search? 🧐
But, what do we want to do with the item once we’ve found it? Sometimes, we simply want to know the index position of the item. Other times, we want to confirm the item exists (or doesn’t exist) in the array. And finally, we may need to use the index position or the knowledge of the items existence in the array somewhere else in our code.
This algorithm is useful when you need to search through a small set of items and when you are only searching for one item. If your array is larger or you need to look for more than one item then I do not recommend the linear search algorithm. In these cases (larger arrays or searching for more than one item), the linear search algorithm becomes wildly inefficient. There are better suited algorithms out there when things get more complicated.
Conclusion 💭
Linear search algorithms are easy to implement and understand. However, since it is a simple loop through an array of items this makes the linear search algorithm inefficient. If we have an array that contains 50,000 elements and the element we’re looking for is in the very last position….we would need to search through every single element before finally reaching the 50,000th element. That is a lot of extra work and time which is why this algorithm isn’t the best. But, we all need to start somewhere when we’re learning algorithms. I think it’s good to understand even the most basic data structures.
You can learn more about the linear search data structure here along with its time complexity in big O notation.
The ELI5 Algorithms Series 📚
Thanks for reading! My name is Halee Pagel (rhymes with Cali Bagel) and I’m a software engineer in Tokyo, Japan. You can find me on twitter which I mostly use for liking tech memes and MLB updates. ✌️
