# Linear search explained

Watch an animation explaining the linear search algorithm, narrated by James Robinson.
2.9
Linear search is a simple search algorithm to understand and implement. It involves checking each item in the list to see if it’s the right one. Let’s have a look at our shelf of sports balls again. The robot arm has been programmed with the linear search algorithm, and has been instructed to find the baseball. It looks at the size of the baseball in its database, and knows that the ball’s diameter is 76 millimetres. So the arm goes to the first ball on the shelf and checks the size of the ball. It’s 218 millimetres, so not the baseball. The arm then moves down to the next ball on the shelf and checks again.
40
This process continues until the correct ball has been found.
46.9
When the correct ball has been identified, it can be picked up by the arm. Whilst in this case finding the ball only took a few moves, it could have taken an incredibly long time if there were millions of balls to search through. The worst case for this algorithm is when the item being searched for isn’t there. Imagine if the robot arm had been told to find a ball that was 60 millimetres in diameter. There isn’t a ball of this size on the shelf. It would have to inspect every ball on the shelf before it could end its search.
82.7
So how could this algorithm be made more efficient? Well, what if we sorted the balls on the shelf first. Now if we asked to search for the ball that’s 60 millimetres in diameter, we can tweak the algorithm, and instruct the arm that if it finds a ball that is larger than 60 millimetres, it can stop its search. The arm is searching for a ball that is equal to or less than 60 millimetres in diameter, rather than exactly 60 millimetres.
112.4
In the next step, you’ll go to implement your own version of linear search using Python. Use the comment section below to check your understanding of the linear search algorithm.

Linear search is a simple search algorithm to understand and to implement. It just involves checking each item in a list in order (hence “linear”) to see if it’s the right one.

Let’s have a look at our shelf of sports balls again. The robot arm has been programmed with the linear search algorithm, and has been instructed to find the baseball. It looks up the size of a baseball in its database, and finds that the ball’s diameter is 76mm.

The arm goes to the first ball on the shelf and checks the size of the ball. It’s 218mm, so not the baseball. The arm then moves down to the next ball on the shelf, and checks again. If this ball is not the baseball, it will move down to the next ball, and check again. This pattern continues until the correct ball has been found and can be picked up by the arm.

While in this case finding the ball only took a few moves, it could have taken an incredibly long time if there were millions of balls to search through. The worst case for this algorithm is when the item being searched for isn’t there. Imagine if the robot arm had been told to find a ball that was 60mm in diameter. There isn’t a ball of this size on the shelf, and the robot would have to inspect every ball on the shelf before it could end its search!

How could this algorithm be made more efficient? We could try sorting the balls on the shelf by size before we searched. Then, if we needed to search for a ball that is 60mm in diameter, we could tweak the algorithm and instruct the arm that if it finds a ball larger than 60mm, it can stop its search. To enable it to do this, at each step, the arm will check if the ball is equal to or less than 60mm in diameter, not just if it is exactly 60mm.

In the next step, you’re going to implement your own version of linear search using Python. In the meantime, use the comments section to share other ideas for contexts or analogies that might help your students understand how linear search works, and its limits.