Introduction
：
/ CSE 331 Homework 2 BinarySearch
\author ___ ___
*/
#include
using std::vector;
/ Recursive Binary Search function ‘Driver.’
**
* Please complete this function *
*
This is the recursive driver. This is where the Binary Search happens.
\param vec The collection we are searching in (in the form. of a vector).
\param item The item we are searching for.
\param start Starting index of the section we are searching. (Default 0)
\param end Ending index of the section we are searching. (Default 0)
\returns The index of the item in vec. -1 if the item is not found.
/
template
int RecursiveBinarySearchDriver(vector vec, const Comparable item,
int start, int end)
{
// Fill in the recursive search here
int mid=(start+end)/2;
if(start!=end)
{
if(item vec[mid])
{
return RecursiveBinarySearchDriver(vec,item,mid+1,end);
}
else
{
return mid;
}
}
else
{
if(item == vec[mid])
{
return mid;
}
else
{
return -1; // must return the index, or -1 if item not found
}
}
}
/ Recursive Binary Search function.
**
* Please complete this function *
*
This function will be what the ‘client’ calls. This function does not
have all the parameters we need to make the correct recursive calls,
so a ‘driver’ method is used to make room for the parameters needed.
The Recursive Binary Search we are implementing has 4 parameters,
this function has two, listed below.
hint: this function is very simple, all the work is done in the driver.
…just call the driver.
\param vec The collection we are searching in (in the form. of a vector).
\param item The item we are searching for.
\returns The index of the item in vec. -1 if the item is not found.
/
template
int RecursiveBinarySearch(vector vec, const Comparable item)
{
// This function will utilize RecursiveBinarySearchDriver to do the
// search. Remember to read the \returns to know what you sould return.
if(vec.size()==0)
{
return -1;
}
else
{
std::sort(vec.begin(),vec.end());
return RecursiveBinarySearchDriver(vec,item,0,vec.size()-1); // must return the index, or -1 if item not found
}
}
/**
This iterative binary search is here as a completed example.
No work needs to be done in this function.
/
template
int BinarySearchIterative(vector items, const int key)
{
insertionsort(items);
int min = 0;
int max = items.size()-1;
int mid;
while(max >= min)
{
mid = (min+max)/2;
if(key items[mid])
min = mid+1;
else
return mid;
}
return -1;
}
:
a) T(n)=T(n/2)+1
b) a=1 b=2 f(n)=1=n0 (0=log21)
∴T(n)=Θ(n0logn)= Θ(logn)
Requirement
HOMEWORK 3 BinarySearch
100 points
DUE DATE: February 16thby 9:00pm.
Homework 3 Deliverables:
● When you have completed your homework, run the following command inside your project
folder to produce your zip file:
○ make submission
● The zip file generated will contain:
○ hw3{YOURNETID}.pdf
○ BinarySearch.cpp
● Your homework folder MUST contain hw3{YOURNETID}.pdf in order for the submission
command to work.
● Upload the generated zip file to d2L. The name of the zip file will be:
○ hw3{YOURNETID}.zip
This is not a team work, do not copy somebody else’s work.
This output indicates your pdf is not present.
This output indicates your pdf is present.
1
Problem 1
The following files are provided:
● BinarySearch.cpp - You will work here.
● Makefile - Used to test/create your submission.
● tests/ folder - Used to test your code. (Recommend not modifying this folder).
In BinarySearch.cpp, your task is to complete the RecursiveBinarySearchDriver and
the RecursiveBinarySearch functions.
Once completed you can use the following command in the project directory (where the
BinarySearch.cpp file is) to test your code:
make
This command will test your code and print the output of the tests (the ones that failed/passed). If your
code does not compile, the output will indicate why.
See the next page for a sample output of the make command.
BinarySearchIterative is provided as a sample of what an iterative version of Binary Search. There is
no need to modify this function and it will not be used during grading. Be careful when you’re
observing this function, if it changes and the syntax breaks, the tests will not compile.
2
3
Problem 2
a)Write the recurrence for your recursive Binary Search method.
Choose one of the following recurrence notation style. shown below, and write your recurrence
for binary search.
Notation 1:
Example T(n) = 2 T(n/4) + n3
Notation 2:
Example:
We will not accept or grade any other notation style.
b) Solve the recurrence you wrote on Problem 2. Use only the Master theorem to solve this
recurrence and show us that it is Θ(lgn). Please show each step clearly, do not just paste the answer,
there will be no points given if you do not show your work.
4