Skip to the main content
PeabodyMake a free story

🤖 Code & Robots, level 6

What the trails say and what they ask. Print it for the class, or put the same questions on the board with a live quiz.

Code & Robots, level 6

🔍 Searching Smart

How can you find one number in a long list without checking them all?

  • How can you find one number in a long list without checking them all? You need a smart plan, and a plan of clear steps that solves a problem is called an algorithm. The simplest search plan is called linear search, where you start at the first item and check each one in order until you find what you want. Linear search always works, even when the list is mixed up, but it can be slow. If a list has 100 items and your number is the last one, you must check all 100 of them. Computers search through huge lists, so coders look for faster plans.
  • If a list is sorted, you can use a faster plan called binary search. Sorted means the items are in order, like numbers going from smallest to largest. First you look at the item in the middle, and if it is the number you want, you are done. If your number is smaller, you can skip the whole upper half, where the bigger numbers are, and if it is larger, you skip the lower half. Then you look at the middle of the part that is left. Each check cuts the list about in half, a bit like opening a dictionary near the middle and flipping toward the right letter.
  • Coders compare plans by counting the steps each one takes. Say a sorted list has 16 items. Binary search cuts what is left about in half with every check, from 16 to 8, then 4, then 2, then 1, so it never needs more than five checks. Linear search might need all 16. The gap grows bigger as lists get longer, so for a sorted list of 1,000 items, binary search needs no more than 10 checks, while linear search could need all 1,000. But remember the catch, because binary search only works on a list that is already sorted.

Try it at home: Play a guessing game: think of a number from 1 to 100 and answer only higher or lower. Can your child find it in seven guesses or fewer by always guessing the middle?

Questions and answers

Searching Smart

  1. A set of clear steps that solves a problem is called… an algorithm (An algorithm is a plan of clear steps that solves a problem.)
  2. 📋 In linear search, where do you start? At the first item (Linear search starts at the first item and checks each one in order.)
  3. A list of 50 names is mixed up, not sorted. Which search can you use? Linear search (Binary search needs a sorted list, but linear search works on any list.)
  4. 🎯 In binary search, which item do you check first? The middle one (Checking the middle lets you skip about half the list at once.)
  5. Sorted list: 2, 5, 8, 11, 14, 17, 20. You want 17, and you check 11 first. What next? Search the right part (17 is bigger than 11, so it must be in the right part, with the bigger numbers.)
  6. ✂️ Each check in binary search cuts the list… about in half (Each check throws away about half of what is left.)