Back to Lesson 24

Exercise 1: Linear search

We can use the following function to perform linear search.

def linearSearch(mylist, elt):
    """
    Performs linear search on a list, looking for a given element elt.

    Returns: the index of elt in mylist, or -1 if it is not found.
    """
    for i in range(len(mylist)):
        if mylist[i] == elt:
            return i
    return -1

What is the output for each of the following examples? Make sure to walk through the code step by step, so you understand what it is doing.

nums = [3, 1, 4, 1, 5, 9, 2, 6, 5]

a = linearSearch(nums, 5)

b = linearSearch(nums, 6)

c = linearSearch(nums, 0)

print(a)
print(b)
print(c)

Ask yourself the following questions:

• Why do we need to iterate through range(len(mylist)) rather than just mylist?
• Why don’t we need an else: continue in the for loop?
• Why don’t we return -1 in the for loop?
• For each input, how many steps does it take to find the answer? (Think of this has how many values do we have to compare to the one we’re searching for.)

Back to Lesson 24

Exercise 2: Binary search

We wrote the following function to perform binary search.

def binarySearch(mylist, elt):
    """
    Performs binary search on a sorted list, looking for a given element elt.

    Returns: the index of elt in mylist, or -1 if it is not found.
    """
    low = 0
    high = len(mylist) - 1

    # Go until the range flips (then you know you haven't found it)
    while low <= high:
        mid = (low+high) // 2 # choose the middle index
        item = mylist[mid]

        if item == elt:  # yay!
            return mid
        elif elt < item: # left half
            high = mid-1
        else:            # right half
            low = mid+1

    # No dice
    return -1

This one is a little more complicated. Also, remember that it requires the input list to be sorted.

What is the output for each of the following examples? Make sure to walk through the code step by step, so you understand what it is doing.

letters = ['a', 'b', 'c', 'f', 'h', 'k', 'o', 'p', 't', 'w', 'z']

res1 = binarySearch(letters, 'a')

res2 = binarySearch(letters, 'y')

res3 = binarySearch(letters, 't')

print(res1)
print(res2)
print(res3)

Ask yourself the following questions:

• What would happen if we didn’t have the if item == elt: return mid lines?
• What would change if we used math.ceil(low+high) / 2) instead of (low+high) // 2 to compute mid?
• What would happen if the list weren’t already sorted?
• For each input, how many steps does it take to find the answer? (Think of this has how many values do we have to compare to the one we’re searching for.)

Back to Lesson 24

Exercise 3: Comparing runtimes

Download and run this program. It will perform both linear and binary search, and plot results comparing their runtimes. Which one runs faster, especially as the number of elements in the list gets very large? How does that compare to your expectations?

Back to Lesson 24