c  go  java  js  lua  py  vbs  rkt  scm  pro  

This page looks at linear search.

The input is in multiple (two) parts so, in this case, two trailer loops are used, one after the other.

Note: Integers are used but larger structure types could be used.

The goal of the program is to read in a sequence of integers - the first list.

Then, another sequence of integers is read in and, for each, it is determined if that integer is in the first list. If it is, then the position in the list is displayed.

For example purposes, input, processing, and output are not fully separated.

Here is some example input, with "..." for omitted parts and the trailer values colorized.

The data structures are as follows.
int x1; int dataLen1; int dataPos1;

dataLen1 = 0; scanf("%d",&x1); while (x1 >= 0) { dataLen1++; data1[dataLen1] = x1; printf("\t%d. %d\n",dataLen1,x1); scanf("%d",&x1); }
The second input of integers is similar.

The result of two ways of searching use the same code for the output (not abstracted in the program since we would only be using one way anyway).
if (dataPos1 == 0) { printf("\t\t%d not found\n",x1); } else { printf("\t\t%d found at #%d\n",x1,dataPos1); }

Here is the search using a compound condition as a (code) guard. Remember, the conjunction condition is short-circuit evaluation.
dataPos1 = dataLen1; while ((dataPos1 != 0) && (data1[dataPos1] != x1)) { dataPos1--; }
A "guard" is a code condition (e.g., Boolean) that guards code from going too far or doing something not to be done.

Note: The value zero (0) can be used to indicate not found since the list is one-based. However, if the list is zero-based, then the not found value might be negative one (-1).

Here is the search using a (data) sentinel at position 0 in the array (since that position is not being used).
data1[0] = x1; dataPos1 = dataLen1; while (data1[dataPos1] != x1) { dataPos1--; }
A "sentinel" is a data value that acts to protect code from going too far or doing something not to be done.

Here is the C code.
#include <stdio.h> int main() { int x1; int dataLen1; int dataPos1; // input and store printf("Input and store:\n"); dataLen1 = 0; scanf("%d",&x1); while (x1 >= 0) { dataLen1++; data1[dataLen1] = x1; printf("\t%d. %d\n",dataLen1,x1); scanf("%d",&x1); } // Input and search printf("Input and search:\n"); scanf("%d",&x1); while (x1 >= 0) { printf("\tSearch for %d\n",x1); // compound condition as guard dataPos1 = dataLen1; while ((dataPos1 != 0) && (data1[dataPos1] != x1)) { dataPos1--; } if (dataPos1 == 0) { printf("\t\t%d not found\n",x1); } else { printf("\t\t%d found at #%d\n",x1,dataPos1); } // using data as sentinel data1[0] = x1; dataPos1 = dataLen1; while (data1[dataPos1] != x1) { dataPos1--; } if (dataPos1 == 0) { printf("\t\t%d not found\n",x1); } else { printf("\t\t%d found at #%d\n",x1,dataPos1); } scanf("%d",&x1); } printf("(done)\n"); return 0; }

Here are some examples of input and output for the above program code.

Here is an example input.
12 23 34 45 56 67 78 89 -1 34 33 55 67 -1
For the above example input, here is the expected output.
Input and store: 1. 12 2. 23 3. 34 4. 45 5. 56 6. 67 7. 78 8. 89 Input and search: Search for 34 34 found at #3 34 found at #3 Search for 33 33 not found 33 not found Search for 55 55 not found 55 not found Search for 67 67 found at #6 67 found at #6 (done)

The next step is to abstract the search functionality into a function.

Here is the abstracted search code that uses a code guard.
int searchDo1(int x1, int *data1, int dataLen1) { int dataPos1; dataPos1 = dataLen1; while ((dataPos1 != 0) && (data1[dataPos1] != x1)) { dataPos1--; } return dataPos1; }

Here is the abstracted search code that uses a data sentinel.
int searchDo2(int x1, int *data1, int dataLen1) { int dataPos1; data1[0] = x1; dataPos1 = dataLen1; while (data1[dataPos1] != x1) { dataPos1--; } return dataPos1; }

Here is the C code.
#include <stdio.h> int searchDo1(int x1, int *data1, int dataLen1) { int dataPos1; dataPos1 = dataLen1; while ((dataPos1 != 0) && (data1[dataPos1] != x1)) { dataPos1--; } return dataPos1; } int searchDo2(int x1, int *data1, int dataLen1) { int dataPos1; data1[0] = x1; dataPos1 = dataLen1; while (data1[dataPos1] != x1) { dataPos1--; } return dataPos1; } int main() { int x1; int dataLen1; int dataPos1; // input and store printf("Input and store:\n"); dataLen1 = 0; scanf("%d",&x1); while (x1 >= 0) { dataLen1++; data1[dataLen1] = x1; printf("\t%d. %d\n",dataLen1,x1); scanf("%d",&x1); } // Input and search printf("Input and search:\n"); scanf("%d",&x1); while (x1 >= 0) { printf("\tSearch for %d\n",x1); // compound condition as guard dataPos1 = searchDo1(x1,data1,dataLen1); if (dataPos1 == 0) { printf("\t\t%d not found\n",x1); } else { printf("\t\t%d found at #%d\n",x1,dataPos1); } // using data as sentinel dataPos1 = searchDo2(x1,data1,dataLen1); if (dataPos1 == 0) { printf("\t\t%d not found\n",x1); } else { printf("\t\t%d found at #%d\n",x1,dataPos1); } scanf("%d",&x1); } printf("(done)\n"); return 0; }

Here are some examples of input and output for the above program code.

Here is an example input.
12 23 34 45 56 67 78 89 -1 34 33 55 67 -1
For the above example input, here is the expected output.
Input and store: 1. 12 2. 23 3. 34 4. 45 5. 56 6. 67 7. 78 8. 89 Input and search: Search for 34 34 found at #3 34 found at #3 Search for 33 33 not found 33 not found Search for 55 55 not found 55 not found Search for 67 67 found at #6 67 found at #6 (done)

4 questions omitted (login required)