Lab 7: Loop Debugging

It's often the case that loops don't work as expected. A common way to debug them is to add print statements to determine where they are going wrong.

Today you will explore this techinque in the context of debugging the following buggy search function.

def binarySearchBuggy(val, sortedElts):
    """
    This is a buggy version of binary search of `val` (any Python
    value) in `sortedElts`, a list of values sorted in ascending
    order.

    If `val` is an element in sortedElts, returns a nonnegative index
    of `val` in `sortedElts`. (If it `val` appears multiple times in
    `sortedElts`, this index can be any of indices at which itp
    appears, not necessarily the least such index.)

    If `val` is not an element in sortedElts, returns -1. 

    To find the index of `val` in `sortedElts`, this function uses a
    binary search technique in which only a subsequence of the values
    in `sortedElts` are considered, and `val` is compared to the
    element at the middle index of this subsequence. This either
    succeeds by finding `val` at this index and return the index, or
    shrinks the range of indices in `sortedElts` that need to be
    checked by about half. If the subsequence becomes empty, -1 is
    returned. The successive halving nature of this algorithm leads
    to a number of steps that is about log_2 of the number of elements
    in `sortedElts`. For a thousand elements, this is about 10 steps;
    for million elements, about 20 steps; and for a billion elements,
    about 30 steps. 
    """
    lo = 0
    hi = len(sortedElts)
    while lo < hi:
        mid = (lo+hi)//2
        midElt = sortedElts[mid]
        if val == midElt:
            return mid # Found it!
        elif val < midElt:
            hi = mid-1
        else: # val > midElt
            lo = mid+1
    return -1

You are provided with the following testBinarySearch function that highlights situations where a binary search function doesn't work. (You don't need to understand all details of this code!)

def testBinarySearch(searchFn, sizeLimit):
    """

    `searchFn` is a any search function that returns the index of a
    value in list of values sorted in ascending order, or -1 if the
    value does not exist in the list.

    `sizeLimit` is a maximum list size to test.

    Creates a sequence of test lists from the empty list to a list of
    length sizeLimit whose elements are even integers beginning with
    10, and test `searchFn` on all integers from 9 up to and including
    the odd integer that's one larger than the last (even) integer in
    the list.

    * If the test succeeds (with either the correct index or -1, as
      determined by Python's .index method on lists), a green
      checkmark is displayed after the correct results.

    * If the test fails, a red X is displayed after the incorrect
      result.

    * If an IndexError (or other exception) is encountered, the
      exception message is displayed. 

    """
    for size in range(sizeLimit):
        print('-'*60) # dashed line between test lists
        testList = list(range(10, 10+size*2, 2))    
        print(f"testList is {testList}")
        for v in range(9, 10+size*2):
            # print(v, end='')
            try: 
                try:
                    expected = testList.index(v)
                except ValueError:
            # .index raises a ValueError rather than returning -1,
            # so handle that here. 
                    expected = -1
                actual = searchFn(v, testList)
                print(f"{v}:{actual}{'✅' if actual==expected else '❌'}")
            except Exception as exn:
                print(f"*EXCEPTION* {exn}")

Copy both of the above functions into Thonny and execute:

testBinarySearch(binarySearchBuggy, 8)

This will highlight situations where binarySearchBuggy doesn't work as expected.

Your goal is to make a copy of binarySearchBuggy named binarySearchCorrect that works correctly. To do this, you will need to figure out why binarySearchBuggy doesn't work! Do this by adding print statements in appropriate lines to figure out why binarySearchBuggy goes wrong and how to fix it!

Table of Contents