Battleships—Learning How Computers Search

What Is This About?

Computers often need to find one piece of information out of a huge pile of data. They need fast ways to do this. This activity shows three ways to search: linear search, binary search, and hashing. (Don't worry — we'll explain what each of those words means!)

Who Is This For?

This works well for kids ages 9 and up. It uses skills like:

• Comparing numbers (bigger than, smaller than, equal to)
• Understanding grids and coordinates (like on a map)
• Thinking things through step by step

What You Need

Each child needs copies of the battleship game sheets:

• Sheets 1A and 1B for Game 1
• Sheets 2A and 2B for Game 2
• Sheets 3A and 3B for Game 3

You might also want some extra copies in case a sheet gets seen by the wrong person!

---

Let's Warm Up First

1. Pick about 15 kids to stand at the front of the room. Give each one a card with a number on it. Mix up the order. Don't let the rest of the class see the numbers!

1. Give another child a small cup with 4 or 5 candies in it. That child's job is to find one certain number. To check a card, they must "pay" one candy. If they find the number before running out of candies, they keep the rest!

1. You can do this again if you like.

1. Now mix up the cards and hand them out again. This time, have the numbered kids line up in order from smallest to biggest. Try the search again.

When the numbers are in order, there's a smarter way to search! Have the child in the middle show their card first. This tells you which half of the line has the number you want. Do this again and again, cutting the group in half each time. This way, you can find the number using just 3 candies instead of many more! You can see right away how much faster this is.

Now Let's Play the Game

Playing the Battleship game will help kids feel how a computer searches for things. While they play, ask them to think about how they are searching — what's their plan?

---

Game 1: Linear Search

How to play:

1. Get into pairs. One person gets sheet 1A, the other gets sheet 1B. Don't show your sheet to your partner!

1. Each of you secretly circles one battleship on the top row of your sheet. Tell your partner the number on that ship (but not where it is).

1. Take turns guessing where your partner's ship is. Say a letter (like "ship C"), and your partner tells you the number written at that letter.

1. Count how many guesses it takes to find your partner's ship. That number is your score.

Let's talk about it:

1. What scores did people get?
2. What is the best score you could get? What is the worst? (Best is 1 guess. Worst is 26 guesses — as long as you don't guess the same ship twice.)

This way of searching is called linear search. That means checking every spot, one after another, until you find what you're looking for.

---

Game 2: Binary Search

This game works the same way as Game 1 — but this time, the numbers on the ships are lined up from smallest to biggest!

How to play:

1. Get into pairs. One person gets sheet 2A, the other gets sheet 2B. Don't peek at your partner's sheet!

1. Each of you secretly circles one ship and tells your partner its number.

1. Take turns guessing letters to find each other's ship.

1. Count your guesses — that's your score.

Let's talk about it:

1. What scores did people get?
2. Which players got low scores? What trick did they use?
3. Which ship should you guess first? (The one in the middle! It tells you which half the ship must be in.) Which one should you guess next? (Again, pick the middle one of whatever half is left.)
4. If you always guess the middle one, how many guesses will you need at most? (Only five!)

This is called binary search — it means splitting the group in half again and again to find what you need much faster.

---

Game 3: Hashing

How to play:

1. Pick a sheet like before and tell your partner the number of your chosen ship.

1. This time, there's a shortcut! You can figure out which column (numbered 0 to 9) the ship is in. Just add up all the digits in the ship's number. Look at the last digit of that sum — that tells you the column!

For example: if the ship's number is 2345, add 2+3+4+5 = 14. The last digit of 14 is 4. So the ship is in column 4!

Once you know the column, you just need to guess which ship in that column is the right one.

This trick is called hashing — because you're squashing (or "hashing") the digits together to get a quick answer.

1. Play the game using this new trick. You can play again using different columns.

Let's talk about it:

1. Share your scores.
2. Which ships were super fast to find? (Ones that were alone in their column!) Which ones were harder? (Ones sharing a column with lots of other ships.)
3. Out of all three ways of searching, which was fastest? Why do you think so?

Here's the big idea: Binary search is faster than linear search, but linear search doesn't need the numbers to be in order first. Hashing is usually the fastest of all three — but sometimes, by bad luck, it can be slow. If all the ships happened to land in the same column, hashing would be just as slow as linear search!

---

Try These Extra Challenges

1. Make up your own battleship games using all three styles. For Game 2, remember to put the numbers in order! Can you figure out how to make the Hashing Game really hard? (Put all the ships in the same column!) How can you make it really easy? (Spread the ships out evenly across all the columns.)

1. What if the ship you're looking for isn't even there? In Linear Search, it would take all 26 guesses to be sure. In Binary Search, it would take 5 guesses. In Hashing, it depends on how many ships are in that column.

1. Using Binary Search, how many guesses would you need if there were 100 spots? (About 6 guesses.) What about 1,000 spots? (About 9.) What about 1 million spots? (About 19!) Notice something cool: the number of guesses grows very slowly, even when the number of spots grows a LOT. Each time the number of spots doubles, you only need one more guess.

---

Why Does This Matter?

Computers store huge amounts of information, and they need to search through it fast. One of the biggest searching jobs in the world happens on the internet — search engines have to look through billions of web pages in a split second! The thing a computer is trying to find — like a word, a barcode number, or someone's name — is called a search key.

You might think computers should just start at the beginning and check everything one by one, like in our first game. But that's actually very slow, even for computers! For example, imagine a store with 10,000 different products. When a cashier scans a barcode, the computer has to search through up to 10,000 numbers to find the right product. Even if checking each one only takes one-thousandth of a second, it could take 10 whole seconds to check the entire list! Imagine waiting that long for every single item in your shopping cart!

A much better way is binary search — sort the numbers in order, then keep checking the middle item to figure out which half to search next. Using this trick, that same store with 10,000 products could be searched in about 14 guesses — taking only two-hundredths of a second. That's hardly any time at all!

A third way to search is called hashing. Instead of checking one by one, the computer uses the search key to figure out exactly where to look. For example, with a phone number, you might add up all its digits and see what's left over when you divide by 11. This works kind of like the "check digit" trick — a small piece of information that comes from the rest of the data.

Usually, hashing finds what it's looking for right away. But sometimes, a few different search keys end up pointing to the same spot — and then the computer has to look a little more carefully to sort them out.