Instructions

Two functions to implement:

1) is_sorted()

The is_sorted() function has one parameter, a list of integers, and returns whether the list is sorted in ascending order. I.e. the function will return True if the numbers are in ascending order, and False if they are not.

An empty list is considered sorted. A list with only one element is sorted.

Note: you cannot use the built-in sorted() function.

2) find()

The find() function has two parameters, a sorted list of integers and a number. The function will return the index where that number is located in the list, or -1 if the number is not in the list.

The algorithm matters here. Since the list is sorted (in ascending order), you don't have to read every single value in the list. An implementation that does not assume the list is sorted could be:

def find(list_of_integers, number):

# Go through the list, one value at a time.

for i, integer in enumerate(list_of_integers):

if number == integer:

# Found element, we can return the index now.

return i

# We went through the whole list and didn't find the number.

return -1

Since the list is assumed to be sorted in this assignment, we can use a better algorithm here (as described during lecture).

The function above would require many comparisons, and is far from optimal when we know the list is sorted. Imagine a sorted list with 10 million elements that does not contain the number 88. The above function would return -1 when we call it to find the index of the value 88 since it does not appear in the list, but it would have required 10 million comparisons (if number == integer), which would have all evaluated to False.

A better algorithm, which assumes the list is sorted, would first check the value of the middle element in the list. If that element is greater than the value we're looking for then we know the element, if it's in the list, is "to the left" of the middle element. This means we we able to "eliminate" half of the values in the list with a single comparison. We can keep repeating that until we find the element (or until we know it's not in the list). For information, finding the index of a value in a 10,000,000-integer sorted list would require less than 25 comparisons.

Hint: use a while loop.

CODE

def is_sorted(list_of_integers): # FIXME (see instructions) if return False

def find(sorted_list_of_integers, number): # FIXME (see instructions) return -1