5.3. Search Algorithms¶
This lesson introduces one common group of algorithms: searches. Through a number guessing game, students explore the efficiency of binary and sequential search algorithms as well as write the pseudocode for binary search.
The Student Lesson: Complete the activities for Unit 5 Lesson 5.3: Search Algorithms.
- Computer lab with projection system
- Video: How Google Search Works
- Binary Game (without feedback)
- Binary Game with too high/too low feedback
- POGIL Worksheet
- POGIL Roles
- Linear/Sequential Search Game
- Slides by Mobile CSP Teacher Mary Rucker
5.3.1. Learning Activities¶
Estimated Length: 45 minutes
- Hook/Motivation (10 minutes): Bring a phonebook or dictionary to class and ask a student look up something in the middle of the alphabet like "lawyer". The student will predictably open the book in the middle using a version of binary search. Ask the other students why didn't the student start at page 1? Ask students to think about how Google is able to search web pages for things like "cat videos" or your name. Show the video on "How Search Works"
- Experiences and Explorations (30 minutes):
- Guessing Game: In pairs, have one student select a secret number between 1 and 100. The other student should try to guess it with as few guesses as possible. Students can let them know if guesses are too high or too low...or correct! Have them switch and repeat the process. Share strategies as a class for guessing the number.
- Explanation: Explain that the students have just used a binary search strategy — guessing in the middle to rule out either the top or bottom half of numbers. This is an efficient strategy because half of the remaining numbers are able to be eliminated with each guess. Now ask students what they think would be the worst strategy for guessing in that it would take the most number of guesses. Hopefully, someone suggests sequential (linear) search — one in which you guess every number starting at one, all the way up to 100.
- POGIL Activity: Divide students into POGIL groups and have them choose roles. Students should work together to answer the questions about binary search, using the widget or by hand. When finished, they should review the widget for sequential search as well.
- Rethink, Reflect and/or Revise (10 minutes): In pairs, have the students write a paragraph giving directions for a sequential search and for a binary search. Share the paragraphs with the class and check for missing details. Have the students complete the interactive exercises and their portfolio reflections.
The College Board's AP Classroom provides a question bank and Topic Questions. You may create a formative assessment quiz in AP Classroom, assign the quiz (a set of questions), and then review the results in class to identify and address any student misunderstandings.The following are suggested topic questions that you could assign once students have completed this lesson.
Suggested Topic Questions:
- Topic 3.11 Binary Search
Assessment Opportunities and Solutions
Solutions Note: Solutions are only available to verified educators who have joined the Teaching Mobile CSP Google group/forum in Unit 1.POGIL Solutions:
- Here is the guessing game pseudocode and an explanation of how binary search works.
- To guess a number between 1 and 100, the maximum number of guesses the algorithm would take is 7 because 100 can be divided into two 7 times before ending up with just 1 number: 100/2 = 50/2 = 25/2 = 13/2 = 7/2 = 4/2 = 2/2 = 1. Or you could compute log2 100 = 7 (rounded up). You could also 27 = 128 and 26 is 64 so to get through 100 numbers by repeatedly halving, it would take at most 7 steps.
- To guess a number between 1 and 500, the maximum number of guesses the algorithm would take is 9 since 29 is 512 or log2 500 = 9. If you repeatedly halve 500 numbers, you would need at most 9 steps to get to 1 number: 500/2 = 250/2 = 125/2 = 63/2 = 32/2 = 16/2 = 8/2 = 4/2 = 2/2 = 1
You can examine students’ work on the interactive exercise and their reflection portfolio entries to assess their progress on the following learning objectives. If students are able to do what is listed there, they are ready to move on to the next lesson.
- Interactive Exercises:
- Portfolio Reflections:
LO X.X.X - Students should be able to ...
Differentiation: More Practice
If students are struggling with lesson concepts, have them review the following resources:
- The Computational Fairy Tales blog (which has a printed book as well) has a number of tales written to illustrate searching, sorting and other programming concepts.
- Binary Search Algorithm on Wikipedia
- Linear Search on Wikipedia
- Interactive binary search demo -- Give a list of state abbreviations arranged in alphabetical order (e.g., CT, NY), this demo traces the binary search algorithm as you search for different abbreviations in the list.
- Binary and Linear Search Algorithms (6:24 video) This videos visually shows how the binary and linear search algorithms are executed. It shows how to search for a particular integer in an array of integers, shows some pseudocode, and talks about the speed and efficiency of each algorithm with comparisons.
- Linear Search (3:32 video) This video provides some real life examples of linear searching along with searching for a number in an array. The video also discusses the pseudocode and how a linear search is performed.
- Guess who? (Interactive game) Guessing game against the computer where asking the right Y/N questions, reduces the list of answers. See also this article which gives a Binary Search strategy for winning at Guess Who?
- Interactive binary search demo with Pascal code -- This demo includes displays the binary search algorithm in Pascal, which isn't all that different from the pseudocode we've used in other algorithm examples.
5.3.2. Professional Development Reflection¶
Discuss the following questions with other teachers in your professional development program.
I am confident I can teach this lesson to my students.
- 1. Strongly Agree
- 2. Agree
- 3. Neutral
- 4. Disagree
- 5. Strongly Disagree