## Introduction

In a linear search, each element of the array is traversed by using iteration. Each element in the traversal is compared against a search key. If the key is found, the location of the array index is returned. If the entire array is traversed without finding the key, dummy value is returned (e.g. -1)

## Linear search Algorithm and Implementation

Given a list of items of a finite size and a Key we traverse the list to find the key and output the **location of the key(s) found in the list.**

**Consider the scenario where we have a list with unique items (in an array) and we wish to find a key.**

**Demonstration in flowgorithm:**

**(Download the Demonstration file here)**

We set up an Real array of size 10 named “list” and initialized with the following values:

**We could implement a function as shown below:**

**Below is an example of how the function can be used:**

### Exercises

- Identify the sentinel variables in the LinearSearch function.
- Show the trace table for all variables found within linear search when the following function calls are made using the array “list” initialized in the figure 1 above:

a) LinearSearch(10,list,300)

b) LinearSearch(10,list,19)

c) LinearSearch(2,list,19)

Hint:

Use the following trace table format:

Step | size | key | SearchResult | i |

1 | ||||

2 | ||||

3 | ||||

4 | ||||

5 |

- Note that an optional column, called “step” is used to keep track of each variable change such that a step is considered to be any time time a variable is initialized or changed.
- You do not need to show the list array.
- Assume that no value is assigned during a variable declaration.

E.g

will not be shown as a step in the trace table.

As an example, this table has been filled to the 4^{th} step for part a) above.

Step | size | key | SearchResult | i |

1 | 10 | |||

2 | 300 | |||

3 | -1 | |||

4 | 0 | |||

5 |

## Updates

2022/02/03 –

Added introductory paragraph: “*In a linear search, each …… is returned (e.g. -1)”*

Added heading “linear search algorithm…..”

© 2020 Vedesh Kungebeharry. All rights reserved.