Searching Algorithms (Battleship)

Objective

Students will learn how computers search for information by exploring and comparing three searching methods: linear search, binary search, and hashing. They will discover why some search methods are faster than others.

Materials

• Copies of the Battleship game sheets (1A/1B for linear search, 2A/2B for binary search, 3A/3B for hashing), enough for each pair of students
• A few spare copies of 1A'/1B', 2A'/2B', 3A'/3B' in case of accidental peeking or extra rounds
• 15 number cards (for the warm-up)
• A small container with 4–5 sweets (or small tokens/counters as a substitute)

Warm-up (~5 min)

1. Choose about 15 children to line up at the front of the classroom. Give each a card with a number on it (in random, unsorted order), keeping the numbers hidden from the class.
2. Give another child the container of sweets. Their job: find a specific number by "paying" one sweet each time they look at a card. If they find it before running out of sweets, they keep the rest.
3. Now have the 15 children sort themselves into ascending order by their numbers, and repeat the search.
4. Point out that when sorted, checking the middle child first lets you eliminate half the group with just one look — this is much more efficient than checking one by one.

Main Activity (~25 min)

Divide the class into pairs and work through the three Battleship games in order. Read the instructions aloud before each game.

Game 1 – Linear Search (Sheets 1A/1B) — ~8 min

1. Each pair gets sheet 1A and 1B (partners must not show each other their sheets).
2. Each student secretly circles one battleship on the top line and tells their partner its number.
3. Taking turns, partners guess the ship's location by naming a letter; the sheet owner reveals the number at that letter.
4. Count the number of shots needed to find the ship — this is the score.
5. Briefly ask: What were the scores? (Minimum possible is 1, maximum is 26, since the ships aren't sorted — this is why it's called "linear" search, going one by one.)

Game 2 – Binary Search (Sheets 2A/2B) — ~8 min

1. Explain that this time the ship numbers are in ascending order.
2. Follow the same steps as Game 1: circle a ship, tell your partner its number, take turns guessing using letters.
3. Count shots used.
4. Discuss briefly: The best strategy is to guess the middle ship first, then the middle of the remaining half, and so on. Using this method, it should take at most five shots. This is called "binary search" because it splits the problem in half each time.

Game 3 – Hashing (Sheets 3A/3B) — ~9 min

1. Explain the hashing rule: add together all the digits of the ship's number. The last digit of that sum tells you which column (0–9) the ship is in.
2. Demonstrate with the example: for ship number 2345, add 2+3+4+5 = 14, so the last digit (4) means the ship is in column 4.
3. Have partners tell each other their chosen ship's number, then use hashing to find the column, then guess within that column.
4. Count shots used and encourage playing more than one round using different columns if time allows.

Wrap-up / Exit Ticket (~10 min)

Lead a short class discussion comparing all three games, then have students answer on paper (or verbally share with a partner):

1. Which method took the fewest shots on average — linear, binary, or hashing?
2. Why does binary search work faster than linear search? (Hint: think about eliminating half the ships at once.)
3. For hashing: which ships were quick to find, and which were harder? (Ships alone in their column are quick; ships sharing a column with many others are harder.)
4. What is one advantage of linear search over the other two? (It doesn't require the ships to be sorted into order.)
5. What could make a hashing game very hard? (If all the ships end up in the same column.)

Collect written answers as the exit ticket, or have pairs share one answer aloud before leaving.

If Time Remains

Have students create their own Battleship game sheet for one of the three formats (linear, binary, or hashing). If they choose the binary search format, remind them the ship numbers must be listed in ascending order. Challenge them: if making a hashing game, can they arrange ship numbers so the game is as hard as possible (all ships in one column) or as easy as possible (ships spread evenly across all columns)?