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

1. Identify the sentinel variables in the LinearSearch function.
   
   
2. 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.