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.

CSP Framework
Big Idea 3: Algorithms and Programming (AAP)
Enduring Understanding AAP-2: The way statements are sequenced and combined in a program determines the computed result. Programs incorporate iteration and selection constructs to represent repetition and make decisions to handle varied input values.
Learning Objective AAP-2.L: Compare multiple algorithms to determine if they yield the same side effect or result.
Skill 1.D AAP-2.L.1 AAP-2.L.5 Essential Knowledge AAP-2.L.1: Algorithms can be written in different ways and still accomplish the same tasks. Essential Knowledge AAP-2.L.5: Different algorithms can be developed or used to solve the same problem.
Learning Objective AAP-2.O.a: For algorithms involving elements of a list: a. Write iteration statements to traverse a list. Learning Objective AAP-2.O.b: For algorithms involving elements of a list: b. Determine the result of an algorithm that includes list traversals.
Skill 4.B AAP-2.O.5 Essential Knowledge AAP-2.O.5: Linear search or sequential search algorithms check each element of a list, in order, until the desired value is found or all elements in the list have been checked.
Learning Objective AAP-2.P.a: For binary search algorithms: a. Determine the number of iterations required to find a value in a data set. Learning Objective AAP-2.P.b: For binary search algorithms: b. Explain the requirements necessary to complete a binary search.
Skill 1.A AAP-2.P.1 AAP-2.P.2 AAP-2.P.3 Essential Knowledge AAP-2.P.1: The binary search algorithm starts at the middle of a sorted data set of numbers and eliminates half of the data; this process repeats until the desired value is found or all elements have been eliminated. EXCLUSION STATEMENT (EK: AAP-2.P.1): Specific implementations of the binary search are outside the scope of the course and the AP Exam. Essential Knowledge AAP-2.P.2: Data must be in sorted order to use the binary search algorithm. Essential Knowledge AAP-2.P.3: Binary search is often more efficient than sequential/linear search when applied to sorted data.

Professional Development

The Student Lesson: Complete the activities for Unit 5 Lesson 5.3: Search Algorithms.

Materials

• 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.

AP Classroom

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 log₂ 100 = 7 (rounded up). You could also 2⁷ = 128 and 2⁶ 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 2⁹ is 512 or log₂ 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

Other Solutions:

• Quizly Solutions
• Portfolio Reflection Questions Solutions

Assessment Opportunities

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.

Differentiation: Enrichment

• 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