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.

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.