Understanding Linear & Binary Search Algorithms

Purpose: To understand the difference between Linear & Binary Searches…and when to use each.

Tower Building Activity
Donald Trump wants to build a tower as quickly as possible. He has unlimited resources and an unlimited budget and is willing to spend any amount to get the job done.
He has chosen to build the tower with blocks that are 5 meters long and 5 meters wide, but only 1 meter tall. The blocks interlock on top and bottom (like Legos). They cannot be stacked sideways.

Goal:
What is the least number of turns that it will take you to build the tower?

Dictionary Word Search – Making Sense out of Linear and Binary Search
Use 2 copies of the same dictionary.

Instructions:

• The Pickers: Hand a dictionary to 2 students and have them pick out a word in the dictionary. They should keep it a secret.
• The Guessers: Select 2 other students who will try to guess what the word is in the least number of attempts. Each of these students will be handed one of the two dictionaries.
• One student will pursue a Linear Search – start at the beginning of the book and ask if each word, as it appears in alphabetical order, is the word they selected.
• The other student will pursue a Binary Search – start with a word in the middle of the Dictionary and ask if the word you are searching for is before or after that word. If before, then go to the half way point between the middle and the start and select a another word and ask if it is before or after that word being searched for. You will slowly narrow in your search.
• Counters: 2 students who will be matched with one of the two guessers. Each one will count how many attempts it takes for the student to narrow in the search.