Modify LinearSearch.cpp and BinarySearch.cpp to display their respective arrays one line at a time using the index as a label for the indexs value. Be on the alert for any errors in the original given version of BinarySearch.cpp. Perform an empirical step count for both binary search and linear search. Use data set sizes of 100, 200, 300, and 400. Indicate how the number of steps relates to the size of the data set.

LinearSearch.cpp

The purpose of this program is to demonstrate linear search. We will create an array and fill it with random numbers and then search for particular numbers in the array. */ #include  // Used for input and output. #include  // Used for getch(). #include  // Used for random number generation. #include  // Used to seed the random number generator. using namespace std; // Forward declarations of functions. void pressAnyKey(); void displayArray(int array[], int length); void randomizeArray(int array[], int length); int linearSearch(int array[], int arraySize, int target); void searchAndDisplayItem(int array[], int arraySize, int target); // Global variables and constants. const int LENGTH = 100; // The length of our demonstration array. int main() { int demo[LENGTH]; // Declare, initialize, and display array. displayArray(demo, LENGTH); pressAnyKey(); // Pause to take in the experience :-). randomizeArray(demo, LENGTH); // Randomize values in array and display. displayArray(demo, LENGTH); pressAnyKey(); // Search for some selected values in our array and display results. int index = linearSearch(demo, LENGTH, 37); if (index >= 0) { cout << "The value 37 was found at index " << index << ". "; } else { cout << "The value 37 was not found in the array. "; } // Use helper function for linear search. searchAndDisplayItem(demo, LENGTH, 43); searchAndDisplayItem(demo, LENGTH, 47); searchAndDisplayItem(demo, LENGTH, 53); pressAnyKey(); // End main function and end program. return 0; } // Display values of array - each on their own line. void displayArray(int array[], int length) { int i = 0; while (i < length) { cout << array[i] << " "; i++; } cout << endl; } // Give a random value to each element of the array. void randomizeArray(int array[], int length) { srand ( (unsigned) time(NULL)); // Seed random number generator. int i = 0; do { array[i] = rand() % 100 + 1; // A random number in the range of 1 to 100 is assigned. i++; } while (i < length); } int linearSearch(int array[], int arraySize, int target) { // Go through each index, one at a time sequentially and check to see if the index's value is the target. for (int index = 0; index < arraySize; index++) { if (array[index] == target) { return index; // Return the index of the found target. } } return -1; // Return -1 as a flag to indicate that the target was not found. } void searchAndDisplayItem(int array[], int arraySize, int target) { // Search for some selected values in our array and display results. int index = linearSearch(array, arraySize, target); if (index >= 0) { cout << "The value " << target << " was found at index " << index << ". "; } else { cout << "The value " << target << " was not found in the array. "; } } // Utility functions. // Press any key to continue. void pressAnyKey() { cout << "Press any key to continue" << endl; _getch(); // Waits and gets next character entered. } 

BinarySearch.cpp

The purpose of this program is to demonstrate binary earch. We will create an array and fill it with random numbers and then search for particular numbers in the array. This program like most programs has a few bugs so be on the look out. */ #include  // Used for input and output. #include  // Used for getch(). #include  // Used for random number generation. #include  // Used to seed the random number generator. using namespace std; // Forward declarations of functions. void pressAnyKey(); void displayArray(int array[], int length); void randomizeArray(int array[], int length); int binarySearch(int array[], int arraySize, int target); void searchAndDisplayItem(int array[], int arraySize, int target); // Global variables and constants. const int LENGTH = 100; // The length of our demonstration array. // Display values of array - each on their own line. void displayArray(int array[], int length) { int i = 0; while (i < length) { cout << array[i] << " "; i++; } cout << endl; } // Give a random value to each element of the array. void randomizeArray(int array[], int length) { srand ( (unsigned) time(NULL)); // Seed random number generator. int i = 0; do { array[i] = rand() % 100 + 1; // A random number in the range of 1 to 100 is assigned. i++; } while (i < length); } int binarySearch(int array[], int arraySize, int target) { int low = 0; int high = arraySize; while (low + 1 < high) { // Choose the middle value of the array's search range. int checkIndex = (low + high) / 2; // Side note: Alternate code int checkIndex = ( (low + high) >> 1); // Shift binary decimal point - it's quicker. if (array[checkIndex] > target) // Is the middle value higher or lower. { high = checkIndex; // Cut search range in half by eliminating the greater than section. } else { low = checkIndex; // Cut search range in half by eliminating the lower than section. } } // Does this save time to check for equality only at the end??? if (array[low] == target) { return low; // Return the index of the found target. } else { return -1; // Indicate that the target was not found. } } void searchAndDisplayItem(int array[], int arraySize, int target) { // Search for some selected values in our array and display results. int index = binarySearch(array, arraySize, target); if (index >= 0) { cout << "The value " << target << " was found at index " << index << ". "; } else { cout << "The value " << target << " was not found in the array. "; } } int main() { int demo[LENGTH]; // Declare, initialize, and display array. displayArray(demo, LENGTH); pressAnyKey(); // Pause to take in the experience :-). randomizeArray(demo, LENGTH); // Randomize values in array and display. displayArray(demo, LENGTH); pressAnyKey(); selectionSort(demo, LENGTH); // Search for some selected values in our array and display results. int index = binarySearch(demo, LENGTH, 37); if (index >= 0) { cout << "The value 37 was found at index " << index << ". "; } else { cout << "The value 37 was not found in the array. "; } // Use helper function for linear search. searchAndDisplayItem(demo, LENGTH, 43); searchAndDisplayItem(demo, LENGTH, 47); searchAndDisplayItem(demo, LENGTH, 53); pressAnyKey(); // End main function and end program. return 0; } // Utility functions. // Press any key to continue. void pressAnyKey() { cout << "Press any key to continue" << endl; _getch(); // Waits and gets next character entered. } // Sort array. void selectionSort(int array[], int length) { int baseIndex, walker, minIndex, temp; // Loop: Traverse unsorted part of array, find minimum value, and swap minimum value into correct position. for (baseIndex = 0; baseIndex < length - 1; baseIndex++) { // Set the initial minimum value as the first position in the unsorted part of the array. minIndex = baseIndex; // Loop: Check each index in unsorted part of array to find the minimum value. for (walker = baseIndex + 1; walker < length; walker++) { if (array[walker] < array[minIndex]) // Check for a new minimum. { minIndex = walker; } } if (minIndex != baseIndex) // Swap to put minimum value in correct position. { temp = array[baseIndex]; array[baseIndex] = array[minIndex]; array[minIndex] = temp; } } }