The code, as provided, will first create an array then populate it with random numbers and print out the first ten elements in the format required for you project. Then it will get a random number that is within the range of elements your array should hold and do a linear search to see if that target value is found. It will do this 5 times. After each search, it will print out the index at which the element was found and confirm this by printing out that element from the array. If NOT FOUND, it will print that instead. See sample output to see what it looks like.

Each time the search executes, it counts the number of steps it took to find (or not find) the target value.

Your job is to figure out how to modify the code so that it prints the total number of steps taken after each iteration. For example, if it finds the first target value in 25 steps and the 2nd value in 100 steps then, after the first iteration, your totalSteps variable will print 25 after the first loop and 125 after the second loop. Keep track of the total number of steps it takes to complete all 5 iterations and then find the average number of steps. Once again, see the sample output to see what your final output should look like.

One suggestion would be to make your totalSteps variable global in scope which can be updated from within your search function. Another suggestion is to modify the search function to take an additional parameter of a pointer or a reference variable which can then update the totalSteps variable via memory reference. There may be other solutions.

Another suggestion would be to modify the SIZE parameter to 10 while you debug your program. Then change it back to 200 when your program is working correctly. It is your program, you can do whatever you want with it. Just make sure you remember what you do so you can change back if you need to.

Once you have completed the lab successfully, you will have much of the code required to complete your project 1. This lab could be modified to perform a binarySearch instead of a linearSearch by first sorting the array and then calling a binary search function instead of the linear search function. We have not covered individual sort routines yet but an example of the use of a sort from the standard template library is included in the code provided and can be used in your project.

Note that you may have duplicate numbers in your populated array. That is normal. It is possible that you can loop through five searches and never find your target value. If that occurs, run your program again until you get at least one of your targets found. They supply that as your output.

Modify linearSearch function so that it updates your totalSteps variable

You may use pointers or reference variables as arguments to the function or

you may move your totalSteps variable to make it global in scope. If you have

some other solution, you may implement that.

Make sure you update the totalSteps before it returns from the function.

Note that there may be more than one location from whence it may return.

include

#include

#include

#include // for std::sort()

int getRandomNumber(const int MY_RANGE);

void printArray(int a[], const int SIZE);

int linearSearch(const int values[],const int n,const int target);

int x = 0;

int main() {

const int SIZE = 200;

const int NUM_SEARCHES = 5;

int * myArray = new int [SIZE];

int totalSteps = 0; // should increase after every iteration of search

srand(time(NULL));

// populate array with random ints from 1 to twice size of array

for(int i = 0; i < SIZE; i++) {

myArray[i] = getRandomNumber(SIZE * 2);

}

// sort array -- must sort before using binary search and does no harm to sort before a linear search

// std::sort(myArray, myArray + SIZE); // uncomment to use sort from STL

// print first ten elements

printArray(myArray, 10);

std::cout << "*********************************** ";

// linear search for a random target value NUM_SEARCHES times

// select a random number within range of array values

for(int i = 0; i < 5; i++){

int target = getRandomNumber(SIZE * 2);

int targetIndex = -1;

//targetIndex = linearSearch(myArray, SIZE, target, totalSteps);

targetIndex = linearSearch(myArray, SIZE, target);

if(targetIndex >= 0){

std::cout << "Target: " << target << " found at index: " << targetIndex

<< " and myArray[" << targetIndex << "]: " << myArray[targetIndex] << std::endl;

}

else{

std::cout << "Target: " << target << " NOT FOUND" << std::endl;

}

std::cout << "totalSteps = " << totalSteps << std::endl;

std::cout << std::endl;

}

std::cout << "Average step count = " << totalSteps / (double) NUM_SEARCHES << std::endl;

delete [] myArray;

return 0;

} // end main()

int getRandomNumber(const int MY_RANGE) {

int randNum = ((rand() % MY_RANGE) + 1); // value between 1 and My_RANGE

return randNum;

}

void printArray(int a[], const int SIZE) {

for(int i = 0; i < SIZE; i++){

std::cout << "a[" << i << "]: " << a[i] << std::endl;

}

return;

}

int linearSearch(const int values[],const int n, const int target){

int stepCount = 0;

for(int i = 0; i < n; i++) {

stepCount += 3; // count if statement, loop comparison, and iteration

if (values[i] == target){

// update totalSteps here...you need to know value before it returns back to main()

return i;

}

}

// update totalSteps here...you need to know value before it returns back to main()

return -1; // target not found

}