Course: Python

Progress (0%)

# Exercise: Linear Search

Exercise 6 Very easy

Prerequisites for the exercise

1. Python Functions
2. Python Control Flow
3. All previous chapters

## Objective

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

## 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

## 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.

"I created Codeguage to save you from falling into the same learning conundrums that I fell into."

— Bilal Adnan, Founder of Codeguage