Skip to 0 minutes and 3 secondsLinear 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.

Skip to 0 minutes and 40 secondsThis process continues until the correct ball has been found.

Skip to 0 minutes and 47 secondsWhen 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.

Skip to 1 minute and 23 secondsSo 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.

Skip to 1 minute and 52 secondsIn 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 explained

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.

A set of 10 sports balls, with a robotic claw above them. The balls in order from the left are a bowling ball, a pool ball, a cricket ball, a ping-pong ball, a baseball, a golf ball, a basketball, a netball, a tennis ball and a soccer ball.

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.

An animated GIF showing the claw checking the size of the first five balls in turn, with the width shown on the claw for each one. The number is red for the first 4 balls, but green for the baseball.

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.

Share this video:

This video is from the free online course:

Programming 102: Think Like a Computer Scientist

Raspberry Pi Foundation