Linear Search

by Mirabelle Jones

Linear search is a simple searching algorithm. In fact, it’s probably the simplest algorithm you’ll learn because it’s so very straight-forward.

You could compare a linear search to going foot-by-foot across a sandy beach looking to see which stretch might contain treasure! This method of searching is slow and careful.

In a linear search, you move from one item to the next in a list, checking each item to see if it’s the one you’re looking for.

Scenario

You might compare this to looking through unlabeled moving boxes for your toothbrush. Because the boxes aren’t labeled, you wouldn’t know where to start exactly. And so to make sure you checked all the boxes, you’d probably want to go through each one, one at a time.

In pseudocode (i.e. not working code), that might look like this:

function findToothbrush(allBoxes, toiletriesBox){
	for(box = 0; box < allBoxes.length; box++){
		if(allBoxes[box] === toiletriesBox) return box;
	}
	return -1; 
}

We start by creating a function called findToothbrush. (Psst: If you aren’t sure what a function is, it’s really just a set of instructions grouped together. We create functions so we can re-use them easily!) Our findToothbrush function has to know where it’s looking (in all the boxes!) and what it’s looking for (the toiletries box which will likely have our toothbrush and all our precious toiletries!) so we give it these two items as parameters:

function findToothbrush(allBoxes, toiletriesBox){

We then need to go through every box and have a look to see if our toothbrush is in there. To do this, we’ll use a for loop which is just a very simple way of doing something over and over again without having to write the same code multiple times. In our for loop, we want to start at the first box (which is box 0 because computers count starting from 0 instead of 1!) and then for each box (meaning while the box we’re looking in is less than the number of total boxes or: allBoxes.length) we want to go from box to box (box++ is how we iterate through the boxes and just means “go to the next box” or box = box + 1).

for(box = 0; box < allBoxes.length; box++){

Then what do we want to do for each box? We want to see if it’s our toiletries box. If it is, we want to know which box it is so we return (meaning we report back) the index where that box is located. In other words we say, “hey the toiletries box is over here—box #3” (for example). If the box we’re looking in isn’t the toiletries box, we check again. We keep doing that until we find our toiletries box.

if(allBoxes[box] === toiletriesBox) return box;}

At the end you see a “return -1” and might be wondering what that’s all about. Well, what if we forgot to pack our toothbrush? We have to have a way of indicating that, so we can end our search. If our toothbrush isn’t in any of the boxes, we would return -1 meaning “our toothbrush isn’t in any box.”

return -1; 

Pretty simple right? Unfortunately, the most straight-forward approach isn’t always the best. Linear search is actually usually pretty slow and not very efficient especially with large lists (think of doing this for a thousand moving boxes…).

For this reason we hardly ever use linear search, but it’s a good place to start because it’s such a familiar, almost “human” approach to searching.

Now that we’ve learned linear search, we’ll move on to another search method that is usually a bit faster: binary search.

If you’d like to learn more about linear search including how to implement it in real code, check out the sections below.

Big O Complexity

Best Case: O(1)

Example: we find what we’re looking for right away!

Worst Case: O(n)

Example: we don’t find what we’re looking for right away and have to search through the list.

Visualizations

From GeeksforGeeks: https://www.geeksforgeeks.org/linear-search/

Pseudocode

1. Create a function that accepts an array (the list of numbers we're looking through) and a value (what number we're looking for) 
2. Using a for loop, go through each item in the array and see if it matches the value we're looking for.
3. If it is, return where we found it (index) in the array.
4. If we never find the value we're looking for, return -1.

Code Examples

Javascript

function linearSearch(arr, val){
    for(var i = 0; i < arr.length; i++){
        if(arr[i] === val) return i;
    }
    return -1;
}

linearSearch([54,5,11,22,37,415,26,38,32], 415)

Sample Problems

Come back soon for these!

More Resources