< Back

Post Lab 10

Handtrace the following code. If there are no errors, your complete handtrace is sufficient. If there are errors, you should annotate the parts of the code which have errors. If necessary, rewrite the entire function.

#Pre:  a_list is a non-empty list of comparable items in sorted order.
#      item is a comparable item.
#Post: Returns True if item is in a_list
fun binary_search(a_list, item):
    mid = len(a_list) // 2
    start = 0
    end = len(a_list)
    while a_list[mid] != item and start < end:
        if a_list[mid] < item:
            start = mid + 1
        else:
            end = mid

        mid = (start + end) // 2

    return a_list[mid] == item

binary_search([1, 2, 3, 4, 5], 3) # True
binary_search([1, 2, 3, 4, 5], 6) # False
binary_search(["a", "b", "c", "d", "f"], "b") # True
binary_search(["a", "b", "c", "d", "f"], "a") # True
binary_search(["a", "b", "c", "d", "f"], "e") # False
					  

Submission

Please complete this worksheet before class on Friday.