Searching Algorithms

Battleships #

Searching for a keyword or value is the basis of many computing applications, whether on an internet search engine or looking up a bank account balance.

This activity explores the main algorithms that are used as the basis for searching on computers, using different variations on the game of battleships.

Activity description (PDF) #

• Instructions for Searching Algorithms activity (English)

Translations and other versions #

• Chinese language version
• Italian language version
• French language version
• German language version
• Turkish language version
• Greek language version
• Portuguese (Brazil) language version
• Russian language version
• Polish language version
• Hungarian language version
• Slovenian Language Translation

Videos #

See our video page.

Photos #

Related Resources #

More lessons and activities #

• Rutgers University Computer Science Department has a binary search activity where students first think how they would search for a song on an MP3 player, and then they learn about binary search.
• The Mathmaniacs web side has a related activity (lesson 8).
• Jeremy Kubica’s Computational Fairy Tales has the following fairy tales/stories that explain the searching algorithms below:
  • Hunting Dragons with Binary Search
  • Breadth First Search and the Pig Thief
  • Minimax Search and the Oracle of Old Toronto

If you want to find out more #

• Wikipedia: Searching Algorithm
• Howstuffworks.com explains the large-scale application of these principles.
• Virginia Tech, Dept of Computer Science has a complete module on Algorithms.

Videos #

• YouTube Search & Discovery – Computerphile
• Video snippets of various algorithms
• MIT Open Courseware in Electrical Engineering and Computer Science has the following lecture Video: Lecture 9: Binary Search, Bubble and Selection Sorts by Eric Grimson and John Guttag

Additional resources #

• Mordechai (Moti) Ben-Ari from the Weizmann Institute of Science, Israel has programmed linear, binary and hashing search in Scratch which can be downloaded in a zip file of the complete set of activities. Please read the ReadMe.txt for documentation.

Curriculum Links #

Great Principles of Computer Science #

• Computation

ACM K12 Curriculum #

• Level I (Grades 3–-5) Topic 11: develop a simple understanding of an algorithm