During class we discussed an implementation of a sequential search algorithm for an array. The code for the algorithm and corresponding main are highlighted below.

#include

using namespace std;

const int ARRAY_SIZE = 10;

int seqSearch (const int lis[], int listLength, int searchItem);

int main() {

int intList[ARRAY_SIZE];

int number;

cout << "Line 15: Enter " << ARRAY_SIZE << " integers." << endl;

for (int index = 0; index < ARRAY_SIZE; index++)

cin >> intList[index];

cout << endl;

cout << "Line 22: Enter the number to be searched.";

cin >> number;

cout << endl;

int pos = seqSearch(intList, ARRAY_SIZE, number);

if (pos != -1)

cout << "Line 29: " << number << " is found at index " << pos <

else

cout << "Line 31: " << number << "" is not in the list" << endl;

return 0;

}

int seqSearch (const int list[], int listLength, int searchItem)

{

int loc;

bool found = false;

loc = 0;

while (loc < listLength && !found)

if (list[loc] == searchItem)

found = true;

else

loc++;

if (found)

return loc;

else

return -1;

}

When you execute this code you should be prompted to enter 10 numbers and a number to search for. If the search number is a part of the array, the index is returned otherwise a -1 is returned.

To increase the number of elements in the array we would need to modify this line:

const int ARRAY_SIZE = 10;

We could definitely do that but think about the implication of what would be involved if we asked a user to enter 100 numbers, 1000 numbers, 10000 numbers. This could result in data entry errors. Lets make some enhancements to the code to reduce the likelihood of data entry errors.

Enhancement #1:

Modify the code so that a random number generator is used to randomly fill the array with numbers in the range of 1..100

As a comment at the end of your code provide a response to the following question: What are some advantages and disadvantages of using this method?

Enhancement #2

Modify the code so that your data is read in from a file

As a comment at the end of your code provide a response to the following question:What are some advantages and disadvantages of using this method?

Now that we have looked at various ways to input values into an array lets focus on the next question: How long does it take to search for a number in an array. Lets find out by adding some timing code. Additions to the original code are highlighted below:

#include

#include

#include

#include

using namespace std;

using namespace std::chrono;

const int ARRAY_SIZE = 10;

int seqSearch (const int lis[], int listLength, int searchItem);

int main() {

int intList[ARRAY_SIZE];

int number;

cout << "Line 15: Enter " << ARRAY_SIZE << " integers." << endl;

for (int index = 0; index < ARRAY_SIZE; index++)

cin >> intList[index];

cout << endl;

cout << "Line 22: Enter the number to be searched.";

cin >> number;

cout << endl;

high_resolution_clock::time_point t1 = high_resolution_clock::now();

int pos = seqSearch(intList, ARRAY_SIZE, number);

high_resolution_clock::time_point t2 = high_resolution_clock::now();

duration time_span_nano = t2 - t1;

duration time_span_micro = t2 - t1;

duration time_span_milli = t2 - t1;

if (pos != -1)

cout << "Line 43: " << number << " is found at index " << pos <

else

cout << "Line 45: " << number << " is not in the list" << endl;

cout << "It took me " << time_span_nano.count() << " nanoseconds to search the array." << endl;

cout << "It took me " << time_span_micro.count() << " microseconds to search the array." << endl;

cout << "It took me " << time_span_milli.count() << " milliseconds to search the array." << endl;

cout << endl;

return 0;

}

int seqSearch (const int list[], int listLength, int searchItem)

{

int loc;

bool found = false;

loc = 0;

while (loc < listLength && !found)

if (list[loc] == searchItem)

found = true;

else

loc++;

if (found)

return loc;

else

return -1;

}

What does the output tell you?

Now lets experiment: how long does it take to search for a number when the list size is:

10:

100:

1000:

10000:

Note: use a random number generator to generate the number; Time will differ based on type of processor you have

Take this data and draw a chart: time vs list size