Objective

Create a function to search for a given value in a list.

Difficulty

Very easy

Description

Suppose we have a given list and we want to check if it has given item in it.

This can easily be done by sequentially iterating over the list and comparing each subsequent item with the item to look for.

An algorithm that operates in this manner in order to search for a value in a list is generally known as a sequential search, or linear search algorithm.

The term 'linear' comes from the fact that the running time of this algorithm can be expressed as a linear function on the length of the list.

In this exercise, you have to create a function linear_search() that implements the linear search algorithm in order to search for an item in a given list.

Its general form should be as follows:

def linear_search(arr, target):
   pass

Two arguments should be provided to the function — the first is the list where to search for the target item, while the second is the item itself.

The function should return True is the target exists in the list, or else False.

Note that the function should search exactly for the target in the list.

Shown below are a couple of examples of the usage of the function:

linear_search([1, 2, 3], 2)
True
linear_search([1, 2, 3], '2')
False
linear_search(['2', '4', '6'], '2')
True
linear_search(['2, 6', '1, 4'], '2')
False
linear_search([False, False, False, True], False)
True
View Solution

New file

Inside the directory you created for this course on Python, create a new folder called Exercise-6-Linear-Search and put the .py solution files for this exercise within it.

Solution

Since we need to go over each and every item of the given list in search of the item to find, we ought to use for. And because we don't need to keep track of the index while iterating over the list, we can directly iterate over the list in for.

So far, this gives us the following:

def linear_search(arr, target):
   for item in arr:
      # Code will go here.
      pass

In each iteration of the for loop, we just need to compare item with target and return True if a match is found.

However, if this if conditional never executes that means that the for loop completes normally and hence execution moves out of it to the next statement inside the function. At this point, we need to return False to signal that there is no match for target in the list.

Altogether we arrive at the following code:

def linear_search(arr, target):
   for item in arr:
      if item == target:
         return True

   return False

This completes our exercise.