PROGRAM SHOULD BE IN C++ and use this searching and sourcecode to do this program

// Lesson #11: Searching and Sorting

//

// Purpose: Code for searching and sorting arrays

//

//

//#include "stdafx.h

#include

#include

#include

using namespace std;

// Function prototypes

void printArray (int array [], int size);

void initArray (int array[], int size);

int linearSearch (int array[], int size, int value);

int binarySearch (int array[], int size, int value);

void swap (int &a, int &b);

void bubbleSort (int array [], int size);

void selectionSort (int array[], int size);

int main()

{

const int ARRAY_SIZE = 20;

int numbers [ARRAY_SIZE];

// Generate array of numbers from 1 to ARRAY_SIZE

initArray(numbers, ARRAY_SIZE);

// Print out Array

printArray (numbers, ARRAY_SIZE);

// Insert code for searching and sorting

// the "numbers" array.

return 0;

}

/******************************

* Print out array elements

******************************/

void printArray (int array[], int size)

{

for (int i=0; i

cout << "array [" << i << "] = " << array [i] << endl;

cout << endl;

}

/******************************

* Initialize array with random numbers

******************************/

void initArray (int array[], int size)

{

unsigned seed = time (0);

srand(seed);

for (int i=0; i< size; i++)

array [i] = 1 + rand() % size;

}

/******************************

* Linear Search

******************************/

int linearSearch (int array[], int size, int value)

{

int index = 0;

int position = -1;

bool found = false;

while (index < size && !found)

{

if (array[index] == value)

{

found = true;

position = index;

}

index++;

}

return position;

}

/******************************

* Binary Search

******************************/

int binarySearch (int arr[], int size, int value)

{

int first = 0;

int last = size -1, middle;

int position = -1;

bool found = false;

while (!found && first <= last)

{

middle = (first + last)/2;

if (arr[middle] == value)

{

found = true;

position = middle;

}

else if (arr[middle] > value)

last = middle - 1;

else

first = middle + 1;

}

return position;

}

/******************************

* Swap two values

******************************/

void swap (int &a, int &b)

{

int temp = a;

a = b;

b = temp;

}

/******************************

* Bubble Sort Algorithm

******************************/

void bubbleSort (int array [], int size)

{

int maxElement;

int index;

for (maxElement = size - 1; maxElement > 0; maxElement--)

for (index = 0; index < maxElement; index++)

if (array [index] > array [index + 1])

swap (array [index], array [index + 1]);

}

/******************************

* Selection sort algorithm

******************************/

void selectionSort (int array[], int size)

{

int minIndex, minValue;

for (int start = 0; start < (size - 1); start++)

{

minIndex = start;

minValue = array[start];

for (int index = start+1; index < size; index++)

{

if (array[index] < minValue)

{

minValue = array[index];

minIndex = index;

}

}

swap (array[minIndex], array [start]);

}

}

Search Benchmarks:

The purpose of this program is to search for a number using the linear and binary search algorithms and report back how many comparisons were done to find a number using both techniques in a sorted array.

Using the Searching and Sorting Source Code that I provided last week (posted on Moodle), modify the MAIN source code to prompt the user to enter a number in the range of 1 to 100 to search for. Then, the program should search an array of sorted numbers for the number using both the linearSearch and binarySearch functions.

For searching, the program should generate a sorted array of integers from 1 to 100 with 100 elements. You can create a new function called initArray2 (the one I provided in the source code is called initArray and can be used to help write initArray2) to initialize the parameter array as follows:

array [0] = 1

array [1] = 2

etc.

until array [99] = 100

Once the number is found in both the linearSearch and binarySearch functions, the functions should print out how many comparisons were done to find the number before returning to the calling function (main).

Input Validation: Do not accept a number to search for that is less than 1 or greater than 100.

Include several test runs of the program to show successful runs of your program, with both valid and invalid data (to show that you are checking for invalid data)

Please ensure the program is well designed and follows accepted style guidelines (e.g. variable naming, indentation, spacing).

Please ensure the program is well documented, including the overall purpose of the program and documenting all the major sections of the code.

NEW: Please ensure your output includes a line that identifies you.