Objectives

• Use Python's random library to generate integers.
• Time program execution with the Python time library.
• Create a program that demonstrates the differing running times of binary search and linear search.

Step 0 - Set up

• Make a lab11 directory in your 201/labs directory
• Change into your lab11 directory.
• Use emacs to create a lab11.py file in your lab11 directory

Overview

• In lecture we saw that linear search has a running time of n, while binary search runs in log ₂ n time.
• Why not use always use binary search if it has a better running time?
• It only works on lists that are sorted.

Program Outline

Pseudo Code

import random and time

Get length of list from the user
Create a list containing the values 0 to length - 1 
Shuffle the list with random.shuffle()

Start linear search timer
Loop 1000 times:
	Generate a random integer between 0 and length - 1
	Call linear search on the list with this random number
Stop linear search timer

Start binary search timer
Sort list with list.sort()
Loop 1000 times:
	Generate a random integer between 0 and length - 1
	Call binary search on list with random number
Stop binary search timer

Print out resulting times

Step 1 - Create List

• We're going to create a list of integers, such that the value stored at each index is the same as the index, i.e. list[5] = 5
• Print the list so you know what the list really contains.
• Next we'll shuffle the values using random.shuffle()
• Print the list so you can see that the values did get shuffled.

Step 2 - Linear Search

• Recall that random.randint(x,y) generates a random integer between x and y inclusive.
• Write a function called linearSearch() that takes a list and a number to search for and returns the index where it was found or -1 if the number was not in the list.
• We'll get a random number in the range of 0 to length - 1 by making a call to random.randint().
• Then we'll search for that number in the list using linearSearch().
• Test this function.

Step 3 - Binary Search

• Copy the binarySearch() function from the Searching Lecture, slide #9. It also takes a list and a number to search for and returns the index where it was found or -1 if the number was not in the list.
• We'll get a random number in the range of 0 to length - 1 by making a call to random.randint().
• Don't forget to sort the list
• Then we'll search for that number in the list using binarySearch().
• Test this function.

Step 4 -
Timing the Execution

• The Python time module can be used to get the current time.
• By storing the time at the start of a block of code and subtracting from the current time at the end, you can determine how much time it took to run.
• time.time() returns the current time in seconds since the epoch, 00:00, January 1, 1970.

Here's an example of timing:

import time

t0 = time.time()
y = 1

for x in range(1000):
    y = y * x
	
t1 = time.time()

print "Execution time:", t1 - t0

• Add code to main() to get the execution times for linearSearch() and binarySearch()
• Remember that since binarySearch() will only work on a sorted list, the timing for binarySearch() should also include the initial sorting of the list.
• Since these execution times will be small, you could get more meaningful data if you time 1000 searches for each type of search.
• Run your program with different size lists to see what the execution times are for both linear search and binary search.