Getting Started (5 min)
Journal: What would be the best way to organize a collection of DVDs so that you could find the one you want very quickly? Discuss.
Class Discussion and Activities (25 min)
Linear Search Discussion (5 min)
As a class, discuss the following question: What is the most effective way to look for an item in an unordered set of values?
- Randomly (How do you stop yourself from repeating yourself?)
Linear Search Activity (5 min)
- Pass out pieces of paper with numbers on them to everyone in the class except one person. Students should not share their numbers with anyone.
- Have everyone stand at the front of the room in a line. The person without a number stands in front and is assigned a number to look for. The class should keep track of how many people they have to ask before they get the number (students that have been checked should sit down).
- Do this activity a few times. In between, each student should switch with another student a couple of times without showing their paper. (Note: A fun way to do this might be a snowball fight if you can)
- Ask for a number that does not exist in the set at least once. What happens? How many people does it take before they figure out the number is not in the set?
- Have everyone sit down but keep their papers.
Binary Search Discussion and Presentation (10 min)
Take out a dictionary (or phone book). Ask the class, how would you search for a particular word/name?
Steps for Binary Search in a book of items to demonstrate to the class:
- Flip to the middle and pick a word in the middle of the page
- Is your word higher or lower than this word? If it is higher, “throw out” the lower half of the book. If it is lower, “throw out” the top half. (Not literally unless it is a very old phonebook. Students do love it when you tear up the phonebook, though, and it makes for a very effective demonstration.)
- Repeat steps 1 and 2 until you find the word.
Why would this not work for an unordered list?
Binary Search Activity (5 min)
- Have everyone go to the front of the room and get in numerical order by paper. Repeat the search activity using the binary search algorithm.
- Try with a number not in the list. How can you tell when it doesn’t exist?
Coding Linear Search (20 min)
- Have students work in pairs to write a code for linear search. The code should:
- Read in a csv file that has a list of unordered numbers. (They should input the file name from the user.)
- Ask the user what number they want to find and validate that number.
- Tell the user whether the number was found. If it was, it should output the number of items it had to look at.
- Students should save their code for the next day.
Note: Skeleton code (SearchCode.py) is provided in the Lesson Resources Folder.
Getting Started (5 min)
- Ask students to list non-numbered, real-world things that they search for or sort/order in their daily lives.
- Can all data be sorted, or do types of data exist that cannot be sorted? How would you organize and search these types of data?
Coding Activity (30 min)
Part 1 Pseudocode (10 min)
- As a class, write down the steps for Binary Search on the board.
- In pairs, have the students write pseudocode for how they would implement binary search.
Part 2 Coding (20 min)
- Students should use their pseudocode to write a program for binary search. (They can also make use of the skeleton code provided for linear search.) The code should accomplish the same things as linear search: read in a file, get a number, and output if the number is found and how many items were checked.
Comparing Searches (15 min) – (May also be Homework if programs are not finished)
- Pass out the worksheet "Search Comparison Worksheet" from the lesson resources folder.
- Students should run both their linear and binary search programs with the six provided datasets of increasing sizes, (also in the lesson resources folder.)
- As they go through, students should record their results in the worksheet and answer the questions at the bottom.
- Discuss the results as a class.
For students that have difficulty understanding the concepts of searching for items in a set of data, pair those students with a student who has a firm grasp of the concept for the activities. Have the pair work together for 1A and then have them keep their own paper secure using the extra game sheet (1A'). Simiilarly for 1B - 1B' and 1C - 1C'.