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)
Translations and other versions
- Italian Language Version
- French Language Version
- German Language Version
- Turkish Language Version
- Greek Language Version
- Portugese (Brazil) Language Version
- Russian Language Version
- Polish Language Version
- Hungarian Language Version
- Slovenian Language Translation
Videos
Photos
Teachers try the battleships game at a conference in Japan
Extension
- An older version of this activity can be downloaded in PDF format here. The content is similar to the current version, but there’s some extra technical information
- 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:
-
- 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 [info]
- Computation
ACM K12 Curriculum [info]
- Level I (Grades 3–-5) Topic 11: develop a simple understanding of an algorithm
New Zealand Curriculum [info]
-
- Mathematics Level 2: Equations and Expressions
- Communicate and interpret simple additive strategies, using words, diagrams (pictures), and symbols
- Mathematics Level 2: Equations and Expressions
-
- Mathematics Level 3: Position and Orientation
- Use a co-ordinate system or the language of direction and distance to specify locations and describe paths
- Mathematics Level 3: Position and Orientation
-
- Technology Level 1: Brief Development
- Describe the outcome they are developing and identify the attributes it should have, taking account of the need or opportunity
- Technology Level 1: Brief Development
-
- Technology Level 1: Outcome Development and Evaluation
- Investigate a context to communicate potential outcomes. Evaluate these against attributes; select and develop an outcome in keeping with the identified attributes.
- Technology Level 1: Outcome Development and Evaluation
- Technology Level 1: Planning for Practice
- Outline a general plan to support the development of an outcome, identifying appropriate steps and resources
