Algorithms and efficiency

Ages 13 to 17 Read alone · about 40 minutes

Read together

Two algorithms can solve the same problem, but one may take far more steps than the other.

Binary search finds an item in a sorted list by halving the possibilities each time.

Do it

1. Write numbers 1 to 100 on cards in order. Ask someone to pick one secret card.
2. Find it by asking 'higher or lower?' starting in the middle. Count the questions.
3. Now find it by going through the cards one by one. Compare the number of steps.
4. Explain why halving is so much faster for large lists.

Talk about it

• How many questions did binary search need?
• What happens with a list of a million?

For the grown-up

This is an unplugged lesson on algorithmic thinking. A list of 100 needs at most 7 halvings, and a list of a million about 20.

Mark as done

← Previous lesson Next lesson →

Where this comes from

• K-12 Computer Science Framework Steering Committee, K-12 Computer Science Framework (2016), concept: algorithms and programming
• Cormen, T. H., Leiserson, C. E., Rivest, R. L., and Stein, C., Introduction to Algorithms (MIT Press, 3rd edition, 2009), chapter on binary search

Written with AI assistance and checked against the sources listed. Please read it before sharing it with a child.