The file list_search.py contains the linear search algorithm we described in class. An algorithm is a sequence of computational steps for completing a task. There are many different algorithms for performing this same task; each has its own advantages and disadvantages over other algorithms. For this section of the lab, you will write a function that searches a list using a different algorithm, binary search.
The binary search algorithm assumes the list is in sorted order. Assuming numeric data, we can sort a list using the sort() method of list, which sorts the list it was called on. You can also use the range() method to generate a sequential list.
Binary search begins by examining the middle element of the list. If that element is the item searched for, then you have found the item. Otherwise, you compare what you are searching for to that middle element. If the middle element is less than the item being searched for, you search the left of the middle element, using the same algorithm. Otherwise, you search right of the middle element, using the same algorithm. You stop when you found the element, or when start is larger than end.
Some other things that you should consider before proceeding. How will
you represent the subset of the list you are examining?
Would the program be any easier to write if
you first create a private helper fucntion to do some of the work? Be
sure to test your code. Create a program that imports binary_search
from list_search.py, creates a sorted, non-random list of
integers, and prints the list and prints True or False if the item searched
for is in the list.
As we discussed in class, we know that binary search SHOULD be faster than
linear search. However, it never hurts to confirm our suspicions. You will do
that now, by writing a program to test our hypothesis. The
timeit module
can be used
to time the execution of code. Read over the documentation for the
timeit module. In particular you will need the Timer initialization
and the timeit method. Also look over the file
timeit_test.py for an example of how to use the
timeit module.
In order to time the search functions, create a new file called
search_timer.py that imports list_search.py,
and contains a class called
SearchTimer. The class should have a list instance variable that
contains a thousand sorted integers. Initialize the list by using
list(range(1000)). Also add two
methods that search the list, one with linear_search and the other
with binary_search. Finally add a method that
uses a Timer to
time the two search functions on sequential lists of 1000 integers.
Run the program several times and notice that the elapsed time is
different every time. Do you know why this is? To compensate for this
variation, the test must be run enough times for the variation to
become small in comparison to the result. Find a value for the number
of executions of timeit such that the faster algorithm's execution
time is at least a millisecond. Is the difference in the algorithms
what you expected? Can you explain the difference?
Let's plot the data, to see the growth of the run-time of the code. Time several runs of both algorithms for each of the following list sizes: 100, 1000, 10000, 100000, 1000000. Each time, search for an item that does not exist within the list. Record the average times you read from your program in LibreOffice Calc, and plot your results. Does your plot look like what we described yesterday? At what point does it seem that binary search becomes better than linear? Include your plot as an image in your lab submission.
The current code to search through a list only applies to objects that can be compared using the <, >, and == operators. However, you've already written a linear search for more complex objects. Recall back in lab0, you wrote a class representing Students for a gradebook. Copy that class into your directory for lab 4. Create a list of Students, similar to what you did for the gradebook. Make sure you insert students in some sorted order. Rewrite your code so that you can use binary search to search through that list of students.
Submit a zip file of your code on the course Inquire site that uses your last names as the file name.