void AList::BinarySearch(int target, bool& found, int&position, int& comparisons
ID: 3617144 • Letter: V
Question
void AList::BinarySearch(int target, bool& found, int&position, int& comparisons)
//Precondition: elements are sorted
//Postcondition: the native object AList is unchanged
{
comparisons = 0;
found = false;
position = BinarySearch(target, 0,numberOfElements-1, comparisons);
if (position != -1)
found = true;
}
// Performs binary search. Returns the index of the firstmatch.
int AList::BinarySearch(int targetElement, int low, int high,int& comparisons)
{
if (high < low)
return -1; // target notfound; return negative index value
int mid = low + ((high-low)/2); // calculate midpoint
comparisons++;
if (elements[mid] > targetElement) {
returnBinarySearch(targetElement, low, mid-1, comparisons);
} else {
//comparisons++;
if (elements[mid] <targetElement) {
return BinarySearch(targetElement, mid+1, high, comparisons);
} else {
return mid; // target found at 'mid' position
}
}
}
// Returns the number of elemenets
Explanation / Answer
void AList::BinarySearch(int target, bool& found, int&position, int& comparisons)
//Precondition: elements are sorted
//Postcondition: the native object AList is unchanged
{
comparisons =0; //initialize counter of number of comarisons to0
found =false; //set found flag to not found
position = BinarySearch(target, 0,numberOfElements-1, comparisons);
if (position !=-1) //set found flag if element found
found = true;
}
// Performs binary search. Returns the index of the firstmatch.
int AList::BinarySearch(int targetElement, int low, int high,int& comparisons)
{
if (high <low) //if beginning and end of where to searchin array overlap - exit element not found
return -1;// target not found; return negativeindex value
int mid = low + ((high-low)/2); // calculate midpoint
comparisons++;
if (elements[mid] > targetElement){ /*if target is in the array split the array in half and search onlythe bottom half of the array since the target element is < thecurrent middle element of the array*/
returnBinarySearch(targetElement, low, mid-1, comparisons);
} else {
//comparisons++;
if (elements[mid] <targetElement) {
return BinarySearch(targetElement, mid+1, high, comparisons);
} else{ //the elementwas found
return mid; // target found at 'mid' position
}
}
}
// Returns the number of elemenets
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.