Goal:
- Students construct their own understanding of the binary search algorithm.
- While this is the purpose of the binary tower activity, it may not work on it’s own so it’s important to have other resources to try.
- Binary search is a fundamental algorithm in computer science.
- Students need to explore the binary search algorithm to see how and why it works before they use it to problem solve.
- After students spend time solving the binary tower activity show the Santa’s Dirty Socks video, which explains this concept by starting with a large number of units and dividing it down until only one unit is left.
- The engaging solution from this video may help students understand the binary algorithm and apply it to the tower lesson.
- Ask students for other examples when they would use the binary search algorithm.
-
Important: Rename the "Trump Tower" in the lesson to "CS Tower."
- Donald Trump has become too political as a result of the 2016 elections and distracts from the important work of the problem.
- Try to quickly guess a number between 1 and 1000 using binary search as an additional activity.
- This can be used before the binary tower activity, in place of it, or after it. It provides an opportunity for students to discover the use of the binary search algorithm for this divide-and-conquer strategy to find a single number.
- Here is how it is done:
- Get students into groups. Have one student in each group secretly pick a number and have the rest of the group guess the number using yes and no questions.
- Groups must count how many guesses it took them to get the right number.
- After groups spend a few minutes guessing their number, hold a class discussion to share the strategies the group used to discover the correct number.
- This video shows a visual explanation on how to use the binary search algorithm to find a name in a phonebook.
- This example is from Harvard’s CS50 course and is a direct lesson in this ECS activity.
- Activity ends at the 25 min mark.
- Here is a great explanation of binary search and how it is used in computer science from Khan Academy.