PLEASE READ ALL INSTRUCTIONS!!! MAKE SURE YOUR CODE COMPILES AND HAS COMMENTS EX
ID: 3539534 • Letter: P
Question
PLEASE READ ALL INSTRUCTIONS!!!
MAKE SURE YOUR CODE COMPILES AND HAS COMMENTS EXPLAINING IT!!!
MAKE SURE IT PASSES THE DRIVESEARCH BELOW AND GIVES THE CORRECT OUTPUT!!!
The value is equal to the middle element. In this case, the element has been found and you are done. Then, return its key.
The value is greater than the middle element, we will consider the right half sub-array of the array
The value is less than the middle element, we will take the left half of the array, before the middle element.
We will keep on repeating the above process with their sub-arrays, until we find the match.
If we can't find the value till the end of the process, it should return -1, which represents there's no such value in the array.
Notice, in the above enumeration, number 1 and 5 would the two base cases in the recursion.
Now, Write a program that implements Binary Search Recursively on Arrays .
Complete the following class "BinarySearch". Please read the comments carefully.
}
We will test your code with class DriverSearch and it should return following output. Remember to return -1, if there is no such element in the array.
} }
Output
2
-1
Explanation / Answer
OK so this is what i got now, it works except when i enter a bigger number than 19, it tells me that the number that is bigger than 19 is found in position 11, but there's no position 11, it only goes to position 10. can you help me fix this small problem, i don't know where it is?
#include <iostream>
#include <cmath>
using namespace std;
// the function
int binarySearch(int L[],int x, int first, int last)
{
if (last >= first) //first > last)
{
//return -1;
int middle = (first + last) / 2;
if (x == L[middle])
return middle;
else if (x < L[middle])
return binarySearch(L, x, first, middle - 1);
else //if(x > L[middle])
return binarySearch(L, x, middle + 1, last);
}
else
return -1;//(first + 1); // failed to find key
}
int main()
{
/* int myList[size] = n;
int myfirst = 0;
int mylast = n - 1;
int findthis;*/
int myList[] = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19};
//int size;
//int myList[size];
//int n = myList[10];
int myfirst = 0;
int mylast = 10;//n - 1;
int findthis;
//int i = 0;
cout << "Please enter a number to find: " << endl;
cin >> findthis;
int resultloc = binarySearch(myList, findthis, myfirst, mylast);
if ( resultloc == -1 )
{
cout << "number not found" <<endl;
}
else
{
cout <<" number is found in position " << resultloc + 1 << endl;//binarySearch(myList, findthis, myfirst, mylast) <<endl;
}
/*if(resultloc == middle)
{
cout << findthis << " was found in position " << middle << endl;
}*/
return 0;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.