This is an assignment for my algorithm class which I have written the code partially and only need to complete it by adding a time function that calculates the average running time. We could use any programming language we want so I am using C++. I am including the instruction and my partial code below. Thank you!

Implement linearSearch(a,key) and binarySearch( a,key)functions.

Part A.In this part we will calculate theaverage-case running time of each function.1.Request the user to enter a positive integer, and call it n.(n =10^5)

2.Generate n random integers between -1000 to 1000 and save them in array a.(You can userandifunction in MATLAB)

3.Sort a(you can use any sorting algorithm you want. If you are using MATLAB, you can call the sortfunction to sort your numbers)

4.Pick a random number in a and save it in variable called key.

5.Call each function separately to search for the keyin the given array.

6.To calculate the average-running time, you need to have a timer to save the total runtime wherepeating step 4 and 5 for 500 times.(tic toc in MATLAB)(Note1:Do not forget to divide the runtime by the number of the times you run step 4-5)

(Note2: Remember to choose a different random number each time you go back to step 4.)

Part B.In this part wewillcalculate theworst-case running timeof each function.

1.Repeat steps1 to 3 inpart A.

2.Now to have theworst case scenario, set the value of the key to 5000 to make sure it does not exist in the array.

3. Run each function once to calculate the worst - case running time when n=10^5.

4.Calculate how much time your machine takes to run one single step.

5.Now estimate theworst-case running time for each algorithm when n = (10^7).

(we've been told to use a hint from homework 3 but there was no information to be found on the homework 3, you can just ignore that part of the queation as I've talked to the instructor)

6.Nowrepeat step 1-3 forn = 10^7 and compare the actual running time with your answer in step 5

=====================

My Partial code:

//Rojin Shahbazian

#include

#include

#include

#include

#include

#include

#include

using namespace std;

const int N = pow(10,5);

int key;

bool LinearSearch(int a[],int key);

bool BinarySearch(int a[], int key)

{

/*

int minimum=0;

int maximum= N -1;

int mid = (minimum + maximum)/2;

bool found = false;

if( a[mid] == key)

{

cout<<" The number was found in array index : " << mid<

found = true;

}

else

{

if (key > a[mid])

{

minimum = mid+1;

mid =(minimum + maximum)/2;

while(!found && minimum < maximum)

{

if (key == a[mid])

found = true;

else if (key > a[mid])

{

minimum = mid+1;

mid =(minimum + maximum)/2;

}

else if (key < a[mid])

{

maximum = mid -1;

mid =(minimum + maximum)/2;

}

}

}

else

{

maximum = mid -1;

mid =(minimum + maximum)/2;

while(!found && minimum < maximum)

{

if (key == a[mid])

found = true;

else if (key > a[mid])

{

minimum = mid+1;

mid =(minimum + maximum)/2;

}

else if (key < a[mid])

{

maximum = mid -1;

mid =(minimum + maximum)/2;

}

}

}

}

return found;

*/

int minimum=0;

int maximum= N;

bool found = false;

while(minimum <= maximum && !found)

{

int mid = (minimum + maximum)/2;

if (key == a[mid])

found = true;

else if (key> a[mid])

minimum = mid +1;

else

maximum = mid -1;

}

return found;

}

/*void Sorted()

{

int array[n];

sort(array, array+n);

}

*/

/*

void merge( int array[n], int l, int m, int r)

{

int i, j, k;

int n1 = m-l+1;

int n2 = r-m;

int L[n1], R[n2];

for(i=0; i

L[i] = array[l+i];

for(j=0; j

R[j] = array[m+1+j];

i=0;

j=0;

k=l;

while(i

{

if(L[i]<=R[j])

{

array[k]= L[i];

i++;

}

else

{

array[k]=R[j];

j++;

}

k++;

}

while(i

{

array[k] = L[i];

i++;

k++;

}

while(j

{

array[k] = R[j];

j++;

k++;

}

}

void mergeSort(int array[], int l, int r)

{

if(l

{

int m = l+(r-l)/2;

mergeSort(array, l, m);

mergeSort(array, m+l, r);

merge(array, l, m, r);

}

}

*/

int main()

{

int array[N];

int min = 2000;

int max = -1000;

srand(time(NULL));

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

{

array[i]= rand()% min+max;

cout<

}

int randIndex = rand()%N;

sort(array,array+N+1);

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

{

cout<

}

int key = array[randIndex];

cout<<"The randomly picked number is: "<

cout<

cout<

int array1[N];

srand(time(NULL));

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

{

array1[i]= rand()% min+max;

cout<

}

sort(array1,array1+N+1);

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

{

cout<

}

int key1 = 5000;

cout<<"The key is: "<

cout<

cout<

}

bool LinearSearch(int a[],int key)

{

bool found = false;

int count = 0;

while(!found && count<=N)

{

if (a[count] == key)

found = true;

else

++count;

}

return found;

}