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:
- 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:
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.
Added introductory paragraph: “In a linear search, each …… is returned (e.g. -1)”
Added heading “linear search algorithm…..”
© 2020 Vedesh Kungebeharry. All rights reserved.