Linear search


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:

array named “list” of size 10 with data values

We could implement a function as shown below:

Linear search function

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

Using linear search on the array “list” with data.


  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)

Use the following trace table format:

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

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

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

2 300  
3  -1 
4   0
Example trace table


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. 

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s