Learn how to implement the linear search algorithm as a function in Python and use it to solve search problems.

Linear Search: Python


The _linear search_ algorithm checks whether a value is an element in a list by scanning the elements of a list one-by-one. 

The algorithm’s iterative approach to finding a target value is useful in solving numerous search problems with unsorted data.

In this lesson, you will learn how to implement the linear search algorithm as a function and use it to solve search problems in Python. 




Introduction

You are a linear search whiz! 

You have implemented linear search as a function in Python and used it to find a  target value, duplicates, and the largest value in different search lists. 

Let’s review what we learned:

 Linear search is a search algorithm that sequentially checks whether a given value is an element of specified list by scanning the elements of a list one-by-one until it finds the target value. 

Starting with linear search as a subroutine in your code is a useful foundation for constructing algorithms to solve more advanced search problems, such as:

* **Finding duplicates** - sequentially search the list for all occurrences of the target value.

* **Finding the maximum value** - sequentially scan the list for the largest value and track the largest value seen to date.

The `linear_search()` function is provided in the text editor. 

Test on your own examples! 


Review

With a few changes to our code, we can modify linear search to solve more complex search problems.

Our linear search function, `linear_search()`, currently finds whether one given value exists in a list, returns the index of the first occurrence of the value in the list, and stops. But what if we wanted to find every occurrence of the target value in a list? 

The following is a list of locations for your favorite music artist’s upcoming tour:

```py
["New York City", "Los Angeles", "Bangkok", "Istanbul", "London", "New York City", "Toronto"]
```

You want to know during which tour stops will your favorite artist be in “New York City”.

Using the linear search algorithm, you can find that New York City will be the first stop on their tour, but the algorithm will indicate that your favorite artist will return to NYC later in the tour. 

In order to find all duplicates of a target value in a list, we modify the algorithm to match the following pseudocode:

```
# For each element in the searchList
  # if element equal target value then
    # Add its index to a list of occurrences
# if the list of occurrences is empty
  # raise ValueError
# otherwise
  # return the list occurrences
```
Let’s implement this in Python. 



Finding Duplicates


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:

```py
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.



Finding the Maximum Value

In the text editor, you will find the code for the `linear_search()` function that we implemented in Python. 

When called, our function returns either an index of an element that matches the target value or a `ValueError` express that the value was not found.

The text editor includes the code for the `linear_search()` function, a list of numbers called `number_list`  and a variable called `target_number`, which stores target value that we will be searching for in `number_list`. 

Let’s practice calling `linear_search()` and explore the return values for different calls to the function.


Using Linear Search

Linear search is used to search for a target value in a list. We examine each of the elements in the list and compare them with the target value until matching the target.

If a match is found, the linear search function will return the index of the matching element. Otherwise, the function will raise a `ValueError`, a special error to indicate that the value was not found.

Here is the pseudocode for linear search as a function:

```
# For each element in the search_list
	# if element equal target value then
	   # return its index
# if element is not found then 
	# raise a ValueError
```


Let’s convert the pseudocode into Python.

