CS 115 Lab 10: Setup and Practice

[Back to lab instructions]

Refer to the Week 12 reading or other resources as necessary to complete this assignment.

Setup

1. If the machine was on when you started using it, reboot it to MacOS.
2. Follow these procedures to mount your blue home-directory on the local machine and create a PyCharm project (call it Lab10). You will use PyCharm in the next part, but, it is important that you set up your project now so that if you run into any issue, we can resolve them quickly.
3. Right-click or control-click to download these 2 files into your default Python directory (C:\Python34 on Windows or Documents on a Mac):
   • cities.txt
   • cities-small.txt

Practice Part 1: The problem of search

This lab is all about different ways of answering one question: If I have a list L and a value v, how can I determine whether v is an element of L, and if so, what its index is?

For example, if I have the list ['A', 'B', 'C'] and the value 'C', my answer would be that 'C' is at position 2 in the list.

The functions we write will return None if the value is not in the list. So if I search the same list for 'D', the answer would be None. Note that None (no quotes!!) is a built-in Python constant just like True and False.

Answer Question 1 in your Moodle writeup.

Practice Part 2: Linear search

If the list is not guaranteed to be in any particular order, we can't do any better than looping through it, looking at each element, and seeing if that element is equal to our desired value.

For example, if we have the list ['A', 'B', 'C'], and we're looking for 'B', we would start by comparing 'B' to 'A'. In the next iteration of the loop, we would compare 'B' to 'B' and return a 1.

However, if we were searching for 'D' instead, we would have to look at every element of the list before reaching the conclusion that 'D' is not present.

Answer Question 2 in your Moodle writeup.

Practice Part 3: Binary search

If the list is guaranteed to be in sorted order, we can actually do better than examining every single element. Here's how:

If we have the list ['A', 'B', 'C'], and we're looking for 'C', and we know that the list is in alphabetical order, we can start by comparing 'C' to the middle element. Since 'C' comes after the middle element alphabetically, we can rule out the element in position 0 without even looking at it. For a longer list, we can keep repeating this trick to cut the list in half, and then half again, and so on.

Answer Question 3 in your Moodle writeup.