The largest value of a sorted list conveniently is the last element of a list. The largest value of an unsorted list, however, is not guaranteed to be the last element.
Imagine that you are a teacher who wants to know the highest score your students scored on a test. Consider the following unsorted list of test scores:
test_scores = [88, 93, 75, 100, 80, 67, 71, 92, 90, 83]
100 is the highest score in the list, but it is the 4th element of the list.
In order to find the highest score, we must sequentially scan the entire list for the largest value and keep track of the largest value that we have seen to date. Using
test_scores, we would keep track of the high score as follows:
- In the first iteration, 88 is the highest test score.
- In the second iteration, 93 is the highest score because it is greater than 88.
- In the third iteration, 93 is the highest score because it is greater than 75.
- In the fourth iteration, 100 is the highest score because it is greater than 93.
This continues until you reach the end of the list.
In order to find the largest value in a list, we modify the algorithm to match the following pseudocode:
# Create a variable called max_value_index # Set max_value_index to the index of the first element of the search list # For each element in the search list # if element is greater than the element at max_value_index # Set max_value_index equal to the index of the element # return max_value_index
Let’s implement this in Python.
We do not need to provide a target value to the function because we’re looking for the largest value.
Change the function declaration of
linear_search() to one parameter,
On the first line within
linear_search(), create a variable
maximum_score_index with a value of
This will track the highest value visited during the search.
As we iterate through the list, we want to check whether each element is greater than the element at
Change the condition of the if statement:
- if the element of
search_listis greater than the element at the
In either of the two conditions:
maximum_score_indexto the index of the current element.
Currently, the linear search function raises a
ValueError after iterating through the list.
Remove that line and return