Searching and The Find Max/Min Algorithm

CS 65: Introduction to Computer Science I

Searching

A search is when you iterate through a collection, looking for values that meet a given critera.

They usually involve

  • a loop that iterates through the collection
  • an if statement that checks each element for that condition

We've used this pattern for solving several different kinds of problems.

  • check if a rainfall amount is in a list of rainfalls
  • checking which movie reviews contain a particular word
  • checking which zipcodes are in a given state
In [1]:
days_of_the_week = ["Sunday","Monday","Tuesday","Wednesday","Thursday","Friday","Saturday"]


for day in days_of_the_week:
    if "S" not in day:
        print(day,"is a good day for programming")

Monday is a good day for programming
Tuesday is a good day for programming
Wednesday is a good day for programming
Thursday is a good day for programming
Friday is a good day for programming

min() and max()

The built-in min() and max() algorithms can find the largest or smallest value in a list.

In [2]:
my_list = [5,1,8,7,4,2]
max(my_list)
Out[2]:
8

How do you think this function works?

It's set up using this search pattern.

Think about how you'd remember the largest value in a list of numbers.

In [3]:
student_grades = [88.3, 53.2, 76.6, 92.2, 81.9, 79.7, 62.1, 84.8, 83.3]
In [25]:
student_grades[8]
Out[25]:
83.3

What was the biggest grade in that list?

At each step, you remembered what the max-so-far was, and you compared it with the new value. At the end, whatever your max-so-far is, is the max of the whole list.

Let's code this up.

In [ ]:
student_grades = [88.3, 53.2, 76.6, 92.2, 81.9, 79.7, 62.1, 84.8, 83.3]

#in-class demo here
In [33]:
#solution 1
max_so_far = -float("inf") #Python's representation of "negative infinity"

for grade in student_grades:
    #if I found a new max-so-far
    if grade > max_so_far:
        #keep track of this value as the new max-so-far
        max_so_far = grade
        
print("The max grade is",max_so_far)

The max grade is 92.2
In [34]:
#solution 2
#in this version we start the max_so_far as the first item in the list
max_so_far = student_grades[0]

for grade in student_grades:
    if grade > max_so_far:
        max_so_far = grade
        
print("The max grade is",max_so_far)

The max grade is 92.2

Group Exercise

What changes do we need to make if we want to find the minimum instead of the maximum?

In [ ]: