Chapter 5.3 - Search Algorithms
Time Estimate: 45 minutes
5.3.1. Introduction and Goals¶
Search is an important area of study in computer science. Just think of how often you search for information on the Internet using Google or some other search engine. It's remarkable how much information Google's algorithms search through and how fast they deliver the results.
Learning Objectives: I will learn to
identify the strengths and weaknesses of the sequential and binary search algorithms
determine the number of steps required to find a value in a data set
Language Objectives: I will be able to
use target vocabulary, such as binary search and sequential search while considering algorithms for finding a value in a data set, with the support of concept definitions and vocabulary notes from this lesson
5.3.2. Learning Activities
As the video above describes, when you do a Google search, you aren't actually searching the Web, you're searching Google's index of the Web. Google's spider programs are constantly traversing the web, collecting millions of web pages and organizing them into an index. When you do a Web search Google's algorithms are searching that index.
What's the best algorithm for searching an index? An index is an ordered collection. Think of the index that comes at the back of a textbook. It is organized in alphabetical order. Each entry in the index refers to some page in the book.
POGIL Activity for the Classroom (15 minutes)
To help you think about the problem of searching an index we're going to play a guessing game. The objective of the game is to come up with the most efficient algorithm for guessing a number between 1 and 100, where most efficient means that it takes the fewest number of guesses.
To play the game you can use the widget below (or open in a new window):
Or, you can play the game without a computer, in which case one team member will think of a secret number between 1 and 100 and the other team members will collaborate to try to come up with the best guess. Just as in the widget, after each guess, the person who knows the secret will tell the guessers whether the guess was too high or too low or just right.
After figuring out a good algorithm, write it in pseudocode.
Break into POGIL teams of 4. Record your answers using this worksheet. (File-Make a Copy to have a version you can edit.)
Role
Responsibility
Facilitator
For each trial of the guessing game, the facilitator records the team's guesses and the result (too high or too low or just right) and keeps track of how many guesses are made.
Spokesperson
Reports the team's pseudocode algorithm.
Quality Control
Tests the algorithm, using the widget or by playing the guessing game by hand.
Process Analyst
Keeps track of the teams progress and assesses its performance and records on the Portfolio the team's answers to the following guided inquiry questions.
Questions
(Portfolio) Define a pseudocode algorithm that will efficiently play the guessing game.
(Portfolio) To guess a number between 1 and 100, what's the maximum number of guesses your algorithm would take?
(Portfolio) To guess a number between 1 and 500, what's the maximum number of guesses your algorithm would take?
Guessing Game: I'll Guess Your Secret Number
One way to look at this game is that we are searching for a number in a list of numbers. Our search made use of the fact that numbers are ordered. The feedback we received – "too high" or "too low" – was based on that order. If you're still working on figuring out an efficient algorithm, maybe the following widget will give you some ideas. Try to observe the algorithm that the widget is using. (Open widget in new window.)
An Efficient Algorithm
There is an efficient algorithm for the guessing game problem, known as the binary search algorithm. It is called binary search because you repeatedly divide the search space into two and eliminate one half of the search space. Click here to see the pseudocode or see the algorithm comparison section below.
Linear (or Sequential) Search
What if you had to search a set of data that was not sorted? Binary search won't work in that case. To illustrate this problem, let's try a variation of our guessing game. This time the app will only tell you if your guess is right or wrong, not whether it is too high or too low. Try it. (Open widget in new window.)
As you can see from this game, if you don't know the order of the items you are going to search, you have no choice but to search them sequentially if you definitely want to find the secret number.
Comparing Linear vs. Binary Search Algorithms
Here is a comparison of sequential search and binary search looking for a target in a list of N items in AP style pseudocode. Don't worry about understanding the details about the binary search algorithm, but do understand the general way it works. Binary search is more complex but it is much faster. However, the list must be in a sorted order for a binary search to work. Linear search is slower but works with any list in any order.
Linear Search Pseudocode
Binary Search Pseudocode
FOR EACH item in List
{
IF (item = target)
DISPLAY "Found target!"
}
low ← 0
high ← N
middle ← item (low+high)/2 (compute the middle of the list, rounded down)
REPEAT UNTIL (middle = target OR low > high)
{
IF (target < middle)
high ← middle - 1 (This cuts off the top half of the list)
IF (target > middle)
low ← middle + 1 (This cuts off the bottom half of the list)
middle ← item (low+high)/2 (compute new middle)
}
IF (middle = target)
DISPLAY "Found target!"
ELSE
DISPLAY "Target not in list"
5.3.3. Summary
In this lesson, you learned how to:
Learning Objective AAP-2.L: Compare multiple algorithms to determine if they yield the same side effect or result.
Algorithms can be written in different ways and still accomplish the same tasks.
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.
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.
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.
Data must be in sorted order to use the binary search algorithm.
Binary search is often more efficient than sequential/linear search when applied to sorted data.
5.3.4. Self-Check
Vocabulary
Here is a table of the technical terms we've introduced in this lesson. Hover over the terms to review the definitions.
binary search
linear or sequential search
Check Your Understanding
Q-1: For searching an unordered list, which search algorithm is the better choice?
A. Binary search B. Linear search
Q-2: For searching a sorted list, which search algorithm is the better choice?
A. Linear search B. Binary search
Q-3: For which of the problems would the binary search algorithm be useful? Choose all that apply.
A. Looking up a person's name in the phone book given the person's phone number.
B. Looking up a word in a Webster's dictionary.
C. Finding the smallest number in a list of numbers arranged randomly.
D. Looking up a phone number in the phone book given the person's full (unique) name.
E. Arranging a deck of cards from the lowest to the highest value cards.
Q-4: For which of the problems could the linear search algorithm be used? Choose all that apply.
A. Looking up a person's name in the phone book given the person's phone number.
B. Arranging a deck of cards from the lowest to the highest value cards.
C. Looking up a phone number in the phone book given the person's full (unique) name.
D. Guessing a secret number between 1 and 100.
E. Looking up a word in a Webster's dictionary.
Q-5: AP 2021 Sample Question: A sorted list of numbers contains 500 elements. Which of the following is closest to the maximum number of list elements that will be examined when performing a binary search for a value in the list?
A. 10
B. 250
C. 50
D. 500
5.3.5. Reflection: For Your Portfolio
Answer the following portfolio reflection questions as directed by your instructor. Questions are also available in this Google Doc where you may use File > Make a Copy to make your own editable copy.
(POGIL) Define a pseudocode algorithm that will efficiently play the guessing game.
(POGIL) To guess a number between 1 and 100, what is the maximum number of guesses your algorithm would take?
(POGIL) To guess a number between 1 and 500, what is the maximum number of guesses your algorithm would take?
Suppose you have a deck of cards and you want to find the Ace of Spades. If the deck is shuffled, which is the best search algorithm to use and why?
Give an example of a search problem you encounter in everyday life. Does it use sequential, binary, or some other search algorithm?
Portfolio Reflection Questions
Make a copy of this document in your Portfolio Assignments folder and answer these questions in the spaces below. Once complete, turn in this assignment according to the steps given by your teacher.
5.3 Search Algorithms Curriculum Page
Answer the following questions:
Questions for the Classroom Activity
1. (POGIL) Define a pseudocode algorithm that will efficiently play the guessing game.
Answer
2. (POGIL) To guess a number between 1 and 100, what is the maximum number of guesses your algorithm would take?
Answer
3. (POGIL) To guess a number between 1 and 500, whats the maximum number of guesses your algorithm would take?
Answer
4. Suppose you have a deck of cards and you want to find the Ace of Spades. If the deck is shuffled, which is the best search algorithm to use and why?
Answer
5. Give an example of a search problem you encounter in everyday life. Does it use sequential, binary, or some other search algorithm?
Answer
Last updated