Binary search of an array using recursive function and pointers

Question

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

Answer 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?

Answer 2

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));
}