Battleships—Finding Things Fast!

What Is This About?

Computers store lots and lots of information.
They need to find things fast.

This game teaches three ways to search.
The ways are called linear, binary, and hashing.

Try This First

Line up some kids at the front.
Give each kid a number card.
Hide the numbers from everyone else.

Give one kid some sweets.
They must find a number.
They can pay one sweet to peek at a card.
If sweets are left over, they keep them!

Now try it again.
This time, line up in order.
Smallest number to biggest number.

Now there's a smart trick.
Peek at the middle kid first.
That tells you which half to search.
Do this again and again.
You can find the number fast!
This way uses fewer sweets.

Game 1: Linear Search

Get a partner.
Each of you gets a game sheet.
Don't peek at your partner's sheet!

Pick one ship.
Circle it.
Tell your partner its number.

Take turns guessing.
Say a letter.
Your partner tells you that ship's number.

Count your guesses.
That is your score!

Talk About It
What scores did you get?
The best score is one guess.
The worst score is guessing every single ship.
This way is called linear search.
You look one by one, in a line.

Game 2: Binary Search

This time the ship numbers are in order.
Smallest to biggest.

Play just like before.
Circle a ship.
Take turns guessing.
Count your guesses.

Talk About It
What scores did you get?
Which ship should you guess first?
Guess the middle ship!
It tells you which half has your ship.
Keep guessing the middle each time.
This way, you can find any ship in just five guesses!

This way is called binary search.
It splits the group in half each time.

Game 3: Hashing

This game has a fun trick.
Add up all the digits in the ship's number.
Look at the last digit of your answer.
That tells you which column the ship is in!

Example: the ship number is 2345.
Add: 2 + 3 + 4 + 5 = 14.
The last digit is 4.
So the ship is in column 4!

Once you know the column, guess which ship it is.

Talk About It
Some ships are easy to find.
They are alone in their column.
Some ships are harder to find.
Their column has many ships.

This way is called hashing.
The digits get squished together to make a clue.

Which Way Is Best?

Linear search is slow.
But you don't need to sort the ships first.

Binary search is faster.
But the ships must be in order.

Hashing is often the fastest.
But sometimes it can be slow too.
If all the ships end up in one column, it is just as slow as linear search!

Why Does This Matter?

Computers store huge amounts of information.
They need to search it very fast.

Think about internet search engines.
They search billions of web pages.
They do it in a tiny piece of a second!

The thing a computer looks for is called a search key.
It could be a word, a number, or a name.

A Real Example: The Supermarket

Imagine a store with 10,000 different products.
Each has a bar code.

With linear search, the computer checks one by one.
This could take ten whole seconds!
That's a long wait at the checkout.

With binary search, it's much faster.
The computer only needs about fourteen checks.
That takes just a tiny bit of time.
You would barely notice!

Hashing Explained More

Hashing uses a math trick on the search key.
For a phone number, you could add up all the digits.
Then divide by 11.
The leftover amount tells you where to look.

This is a bit like the check digits from another lesson.
A small piece of data gives you a big clue!

Usually, the computer finds things right away.
Sometimes, two things land in the same spot.
Then the computer needs one more small step to sort it out.