+ 2

Binary search of an array using recursive function and pointers

Having an assignment where I have to do a binary search of an array using recursive functions and pointers (Yes, its easier without pointers, but that's what the assignment is) I can't seem to get it to work, and I'm at a loss. It seems to default to false all the time bool containedInSortedarray(int x, const int* pBegin, const int* pEnd) { assert(pEnd-pBegin != 0); //Checks if array is empty if (pEnd-pBegin == 1 && *pBegin == x) //Base case return true; if (pBegin < pEnd){ int midPoint = (*pBegin + *(pEnd-1) / 2); if(midPoint == x) return true; if(*pBegin > x) return containedInSortedarray(x, pBegin, pEnd - midPoint); else if(*pBegin < x) return containedInSortedarray(x, pBegin + midPoint, pEnd); } return false; } int main(){ int x = 2; const int size = 9; int sampleArray[size] = {1,2,3,4,5,6,7,8,9}; assert(containedInSortedarray(x, &sampleArray[0], &sampleArray[size])); return 0

30th Jan 2022, 5:51 PM
Erik Pettersson
Erik Pettersson - avatar
2 Réponses
+ 1
G'day Erik Pettersson could you please copy your code into a SoloLearn "code bit" and then update you post to have that as a link? I've not been doing C++ , but I'm certain that your copy/paste code is missing preprocessors and etc. Would you also have some test data in your code comments for us to see what it should be working with?
30th Jan 2022, 7:04 PM
HungryTradie
HungryTradie - avatar
+ 1
Erik, I changed this a bit so I could visualize it, you can change it back to assert. int containedInSortedarray(int x, int* searchArray, int arrSize) { //Has the beginning and end past over if(arrSize < 0) return 0; //Does the item at pointer equal x if(*searchArray + (arrSize / 2) == x){ return 1; //If not is the value larger? } else if(x > *searchArray + (arrSize / 2)){ // If it is larger move the beginning pointer to the middle and decrease the size containedInSortedarray(x, searchArray + (arrSize / 2), (arrSize % 2 == 0) ? (arrSize / 2) : ((arrSize / 2) + 1)); } else { //If it is smaller leave the beginning pointer only reduce the size containedInSortedarray(x, searchArray, (arrSize % 2 == 0) ? (arrSize / 2) : ((arrSize / 2) + 1)); } } int main(){ int x = 10; //Keep changing the numbers to see it work const int size = 9; int sampleArray[] = {1,2,3,4,5,6,7,8,9}; //Putting size in the [] created errror printf("%d", containedInSortedarray(x, &sampleArray[0], size)); }
30th Jan 2022, 8:01 PM
William Owens
William Owens - avatar