#include

#include

using namespace std;

// Checks to see if item is in a vector

// retruns true or false (1 or 0)

//using sequential Search

bool sequentialSearch(vector avector, int item) {

unsigned int pos = 0;

bool found = false;

while (pos < avector.size() && !found) {

if (avector[pos] == item) {

found = true;

} else {

pos++;

}

}

return found;

}

bool binarySearch(vector avector, int item) {

int first = 0;

int last = avector.size() - 1;

bool found = false;

while (first <= last && !found) {

int midpoint = (first + last) / 2;

if (avector[midpoint] == item) {

found = true;

} else {

if (item < avector[midpoint]) {

last = midpoint - 1;

} else {

first = midpoint + 1;

}

}

}

return found;

}

bool binarySearch(vector alist, int item) {

if (alist.size() == 0) {

return false;

} else {

int midpoint = alist.size() / 2;

if (alist[midpoint] == item) {

return true;

} else {

if (item < alist[midpoint]) {

vector lefthalf(alist.begin(), alist.begin() + midpoint);

return binarySearch(lefthalf, item);

} else {

vector righthalf(

alist.begin() + midpoint + 1, alist.end());

return binarySearch(righthalf, item);

}

}

}

}

int main() {

// Vector initialized using an array

int arr[] = {1, 2, 32, 8, 17, 19, 42, 13, 0};

vector testvector(arr,arr+(sizeof(arr)/sizeof(arr[0])));

cout << sequentialSearch(testvector, 3) << endl;

cout << sequentialSearch(testvector, 13) << endl;

// Using static array to initialize a vector

static const int arr[] = {0, 1, 2, 8, 13, 17, 19, 32, 42};

vector avector(arr, arr + sizeof(arr) / sizeof(arr[0]));

cout << binarySearch(avector, 3) << endl;

cout << binarySearch(avector, 13) << endl;

// Using static array to initialize a vector

static const int arr[] = {0, 1, 2, 8, 13, 17, 19, 32, 42};

vector alist(arr, arr + sizeof(arr) / sizeof(arr[0]));

cout << binarySearch(alist, 3) << endl;

cout << binarySearch(alist, 13) << endl;

return 0;

}

Add the necessary include/using lines at the top, and add a main().

In main(), create a vector of 500 random ints. Then create a vector that contains every 50th int from your first vector, as well as 10 newly generated random numbers (so the second vector will contain 20 ints).

Then set up a loop to go through the second vector, and use each item as the item you are searching for using each of the three search algorithms. Time each algorithm, and print out a message such as the following (actual values for the timing will vary) for each item you search for, and then the average times for found vs. not found items:

Value: 21, FOUND

Sequential time: ...

Iterative binary time: ...

Recursive binary time: ...

Value: 8, NOT FOUND

Sequential time: ...

Iterative binary time: ...

Recursive binary time: ...

...

Average for FOUND items:

Sequential time: ...

Iterative binary time: ...

Recursive binary time: ...

Average for NOT FOUND items:

Sequential time: ...

Iterative binary time: ...

Recursive binary time: ...