PDE - Linear or Sequential Search (Lesson)

Linear or Sequential Search

Traversing in the Order Given

This type of search, linear/sequential looks through the data collected from the beginning, index 0, to the end length -1, until the information that is being searched for is found or the data set has no more data. Then a result can be returned to let the calling statement know if the information is there or not. 

Data stored in the array or list could be either ordered or unordered for this search.  The first data item is checked, then the second, etc. until the array is exhausted or the data item found.

If additional data is required to be collected during the search on the value in question, like how many occurrences of the value exist, this data can be collected using the same search by implementing one or more collection variables to keep track of this new required information.

Linear Search 1: Existence -- Does the Number Exist in the Array?

Notes:

  • The delay is used to help with recording.
  • The random pull of a number to search for.
  • The call to the method, in this case, a get function created for the search of the code below.
  • The return type of the catching variable which means the get function must also have the Boolean return type.
  • The parameters passed
    • randomArray - the array to use to look for the number.
    • nbrToFind - the number that the method will determine exists in the array.
    • TotalNbrs - the total number of indexed positions used in the random array (see earlier references in userInput page).
  • The return value is a boolean and usable.

LinearorSequential1.jpg

Linear Search 2: More than Existence --  How many of the number searched for exists in the array?

Notes:

  • The delay is used to help with recording.
  • The random pull of a number to search for.
  • The call to the method, in this case, a get function created for the search of the code below.
  • The return type of the catching variable which means this get function must also have a whole (integer) number return type.
  • The parameters passed
    • randomArray - the array to use to look for the number.
    • nbrToFind - the number that the method will determine exists in the array.
    • TotalNbrs - the total number of indexed positions used in the random array (see earlier references in userInput page).
  • The return value is a number and usable.

LinearorSequential2.jpg

getFunctions Called

Each of the get functions called above are using the search method of looking for the item to be found, one data index position at a time starting from lowest to highest.  Could we have started from highest to lowest?  Of course, but the structure of the loop would change to accommodate the length -1 and going backwards through the array.  Remember we learned this when setting up and reading the original random array creation which was used as the front end to load these arrays for the searches.

In this area the call to the get function, getLinearSearchBoolean or getLinearSearchCount is placed prior to the actual method.  This is good practice for documentation as this shows usage of the method (whether a procedure or a getFunction as shown here).

getLinearSearchBoolean

The purpose of the getLinearSearchBoolean method is to locate whether the number passed to the method in the parameter nbrSearch is in the array randomLinearArray, another parameter in the method.  The incoming array has 10 positions, the number of positions used adjusted by the user when the array is set up.  Passing the arrayUse parameter ensures that only the index positions in use are used to locate the nbrSearch rather than the default length of the array.  Functionally, getLinearSearchBoolean reads the array beginning at the first position, index 0, until there is a match for the number being searched for, nbrSearch. The while loop, controlled by the index, is always less than the arrayUse parameter and only incremented by 1 as the last statement in the loop.  The decision inside the loop tests if the nbrSearch matches an array number, if so nbrFound is set to true to pass back to the call statement.  If nbrSearch is not found, the default setting of false for nbrFound is sent back to the call statement after the complete array is checked.  Exiting the method as soon as the number is found will save computer processing time and provides reliability. 

Notes:

  • Word count above is 199 providing purpose (what it accomplishes), functionality (how it works) and addressing complexity.  Note detail with names is used. 
  • Creating the method itself also reduces complexity as the code may be called multiple times, but any debug or adjustments needed are only done once.
  • Names used here that are the same as used in other areas fo the program do not cross into a method unless you pass them in.  So, index and notFound if used in both places must be declared and assigned an initial value. This is called an assignment statement.
  • This get method has a way to get out as soon as the item is found, providing time efficiency especially for large data sets.

LinearorSequential3.jpg

LinearorSequential4.jpg

getLinearSearchCount

getLinearSearchCount

The purpose of the getLinearSearchCount method is to return how many times the number passed to the method in the parameter nbrSearch is found in the array randomLinearArray, another parameter in the method.  The array has 10 positions, the number of positions used adjusted by the user when the array is set up.  Passing the arrayUse parameter ensures that only the index positions in use are used to locate the nbrSearch rather than the default length of the array.  Functionally, getLinearSearchCount reads the array beginning at the first position, index 0, checking for the decision match for nbrSearch and the array data.  A match adds one to the variable countSearchNbr and the loop continues to the end of the arrayUse numbers.  The while loop is controlled by the index always less than the arrayUse parameter and incremented by 1 as the last statement in the loop to read the complete array.  Exiting the loop, the return is the countSearchNbr, the number of times the number nbrSearch appeared in randomLinearArray. Using a method reduces complexity of the program by allowing this code to be called for multiple arrays or multiple times.  The single place for the code allows debugging and fixing time to be at a minimum, fixing all calls at the same time.

with 

getLinearSearchCount

The purpose of the getLinearSearchCount method is to return how many times the number passed to the method in the parameter nbrSearch is found in the array named randomLinearArray, another parameter in the method. 

The array has 10 positions, the number of positions used, adjusted to the actual number of positions used in the array, 1 to 10.  The user chould have chosen to only use 5 positions in the array that could have held 10.  Passing the arrayUse parameter ensures that only the index positions in use are used to locate the nbrSearch rather than the default length of the array.  

Functionally, getLinearSearchCount reads the array beginning at the first position, index 0, checking for the decision match for nbrSearch and the array data.  A match adds one to the variable countSearchNbr and the loop continues to the end of the arrayUse numbers. 

The while loop is controlled by the index which is checked against the arrayUse parameter and incremented by 1 as the last statement in the loop to read the complete array.  When the index reaches the value of the arrayUse parameter, the loop is exited. 

Exiting the loop, the return out of the method back to the calling section of the program is the countSearchNbr, the number of times the value in nbrSearch appeared in randomLinearArray.

Using a method reduces complexity of the program by allowing this code to be called for multiple arrays or multiple times.  The single place for the code allows debugging and fixing time to be at a minimum, fixing all calls to the array, with the single fix to the array. 

Notes:

  • Variable names used in the method that are the same variable names used in other areas of the program do not cross into a method unless you pass them in.  If the index and notFound variables are used in multiple places ypu must be careful to declare and assign an initial value for the method. Assigning an initial value is a declaration assignment statement as this declares the type of variable and the beginning value of the variable.
  • In the get method,  a way to get out of the method as soon as the item is found is available, providing time efficiency especially for large data sets.

LinearorSequential5.jpg

LinearorSquential6.jpg

Comparison Analysis

Above there are two different calls to get function methods (a getter because there is a value that needs to be returned to solve the problem).  The two get functions are similar but different.  The difference is based on what the programmer needs to get back.  

  1. Could one get function have been written and a result of zero tested and used to mean that the number did not exist in the array? Absolutely!  
  2. What would possibly be lost if the two get functions were combined?  Time in terms of exit for the getLinearSearchBoolean or complexity in programming to have a solution to both.
  3. Could the two get functions have used different parameter names for the method parameters?  Certainly, but consistency allows for quicker programming and design without added unnecessary overhead of a myriad of names that all mean the same thing.

Videos of the test runs for the above two return methods (getters).

In all of these videos and code shown above, various debugging techniques are shown to allow a trace of the code with the video. Though standardly we would turn this techniques off for the final code, they have been left here to allow you to trace the path of the program and analyze why different paths were taken.

getLinearSearchBoolean - Finds Number                                                                          getLinearSearchBoolean - Does Not Find Number              

getLinearSearchCount - Finds Number                                                                          getLinearSearchCount - Does Not Find Number  

Interesting Notes for Thought

  • Testing should always include all cases, even the not found case as noted here to test all of the code.
  • Why does the random pull not always pull all of the numbers 1, 2, 3  when the number of numbers to use between 1 and 3 inclusively is used for the random pull?
  • Can the same number be pulled each time to be put in the array?  Yes, see video below.

IMAGES & VIDEOS CREATED BY GAVS.