CS21 Week 10: Searchin
Week 10 Topics
Motivation for search
Complexity of linear search
Complexity of binary search
Computer Science as a discipline is focused on two primary questions:
What types of problems can be solved computationally?
How efficiently can these problems be solved?
One of the core problems we computers are asked to solved is the search problem. Broadly speaking, the search problem searches for a query item in a (potentially very large) set of potential matches. For two large internet companies, search is one part of their core business model.
Searching efficiently can help you solve larger problems, help more customers, or make larger profits. So how do we organize data and write code/algorithms to search efficiently? And what do we even mean by efficient?
Consider the two game modes in your number guessing game — the modes differ slightly in how they give you feedback when your guess is wrong. Try playing both games. Do you have a different strategy for one game than the other? Why?
Motivating example: Number Guessing Game
To help us with our upcoming analysis of searching, let’s consider a number guessing game,
guessing.py. Here are the rules:
At the start, the program asks the user which mode to play the game in:
The game then chooses a random
targetnumber between 0 and 200.
The game then repeatedly prompts the user for a guess of the number. It checks the user’s number against the
target. If they match, the user has won and the game ends. Otherwise:
In easy mode, tells the user whether the
targetis lower or higher than the value they entered.
In hard mode, just tells the user whether the guess was right or wrong, but doesn’t give any additional hints or feedback.
An implementation of this game has been provided to you, but for extra practice try doing the design and implementation of this game yourself!
To practice top-down design, start by working with a neighbor to design your
main() function and sketch out all the functions that
main() will need to
call. Be sure to consider the types of all function parameters and return
values, noting them in comments associated with each function.
After you have completed the design, implement the program and test it.
For an extra challenge, think about how you might add another game mode: either
extra easy or
extra hard, and implement one such mode if time permits.
In addition to learning and coding a few searching and sorting algorithms over the next two weeks, we’ll also start analyzing algorithms. We can analyze and compare algorithms by classifying them into broad complexity categories so we can compare one type of algorithm to another without worrying about details like implementation language used or speed of the physical machine.
To analyze the complexity of an algorithm, we need to consider several questions. For now, we’ll think about these in the context of searching, but these idea apply much more generally too:
What are the resources are we trying to optimize for? (e.g., minimize time to win the game, minimize CPU time, minimize memory usage)
How do we analyze how long it takes for an algorithm to finish?
If we want to count the "steps" needed to complete a task, what counts as a step? (e.g., number of guesses, number of comparisons made in a search)
Do we care about the best case scenario, what happens on average, or the worst case?
Let’s draw a rough analysis of our guessing game on the board.
To explore the complexity of search, we will narrow the problem to searching
for an item
x in a python list of items. Python already has two ways of doing
this. The first is the Boolean
x in ls which returns
x is in the list
False otherwise. Python also supports the
index() method which will tell you the position in the list of the first
x appears in the list. So
return an integer position if
x is in
x is not in the list,
Python will generate an error called an exception that will likely crash your
program since we have not talked much about how to handle exceptions in this
But how do these methods actually work? At some point, a computer scientist and
python programmer designed and wrote the code for these built-in features. We
will discuss the algorithm for searching a collection of items. Together,
we’ll write a function that does something familiar: search through a list for
an item without using the
in operator. Our functions will be called
Complete the program
This program reads a list of numbers from a file
It then prompts the user for a number, and then searches through the numbers
to see if the user’s selection is present
A key algorithmic question is: can we do better? In some cases, we can’t (and we can prove this!). In the case of linear search, we cannot do better in the general case (i.e. for any type of problem we might want to use search for). However, if all items in the collection are in sorted order, we can perform a faster algorithm known as binary search.
Binary search works using divide and conquer approach. Each step of the algorithm divides the number of items to search in half until it finds the value or has no items left to search. Here is some pseudocode for the algorithm:
set low = lowest-possible index set high = highest possible index LOOP: calculate middle index = (low + high) // 2 if item is at middle index, we're done (found it! return matching index) elif item is < middle item, set high to middle - 1 elif item is > middle item, set low to middle + 1 if low is ever greater than high, item not here (done, return -1)
How and why does this algorithm work?
Why does it require the list to be in order before we begin?
Why is this faster than linear search?
How much faster will it be?
File I/O using objects
We’ve seen how to read CSV files into a list of strings, but that’s often awkward to work with. As a result, we may want to convert each "line" of the file (which is a comma-separated string) into an object:
.split(",")method to divide a line into fields
Cast the non-string members to the correct type
Then feed them into the constructor for an object
For an example of this, check out