CS21 Week 10: Searchin
Week 10 Topics

Motivation for search

Linear search

Complexity of linear search

Binary search

Complexity of binary search
Monday
Search Motivation
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?
As concrete examples, Google once found that a halfsecond delay caused a 20% drop in traffic, and 100 extra milliseconds of page load time reduced Amazon’s revenue substantially.
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:
easy
orhard
. 
The game then chooses a random
target
number 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
target
is 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.

Extra Practice
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 topdown 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.
Implementation
After you have completed the design, implement the program and test it.
Bonus
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.
Algorithmic Complexity
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.
Linear Search
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 in
operator, x in ls
which returns True
if
x
is in the list ls
and False
otherwise. Python also supports the
index()
method which will tell you the position in the list of the first
occurrence of x
, provided x
appears in the list. So ls.index(x)
will
return an integer position if x
is in ls
. If 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
class.
But how do these methods actually work? At some point, a computer scientist and
python programmer designed and wrote the code for these builtin 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
contains
and position_of
.
Example program

Complete the program
linear_search.py

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
Wednesday
Binary Search
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 = lowestpossible 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?
Friday
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 commaseparated string) into an object:

Use the
.split(",")
method to divide a line into fields 
Cast the nonstring members to the correct type

Then feed them into the constructor for an object
Example
For an example of this, check out read_objects.py