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

Did you step through the code line by line using a debugger? What did you observe? — CherryDT, Jan 30 '22 at 17:50
I don't believe you've decided whether `midpoint` is an index into the array or a value to be compared against values in the array. [Run this code in a debugger](https://stackoverflow.com/questions/25385173/what-is-a-debugger-and-how-can-it-help-me-diagnose-problems) to see for yourself. — Drew Dormann, Jan 30 '22 at 17:54

Vlad from Moscow · Answer 1 · 2022-01-30T19:00:55.543

This statement

int midPoint = (*pBegin + *(pEnd-1) / 2);

does not make a sense. You need to determine a pointer to the middle element of the range. As a results these recursive calls

    if(*pBegin > x)
        return containedInSortedarray(x, pBegin, pEnd - midPoint);
    else if(*pBegin < x)
        return containedInSortedarray(x, pBegin + midPoint, pEnd)

have invalid arguments.

The function can be defined the following way

#include <iterator>

//...

bool containedInSortedarray( const int *pBegin, const int *pEnd, int x )
{
    if ( pBegin == pEnd )
    {
        return false;
    }

    const int *pMiddle = std::next( pBegin, std::distance( pBegin, pEnd ) / 2 );

    if ( x < *pMiddle )
    {
        return containedInSortedarray( pBegin, pMiddle, x );
    }
    else if ( *pMiddle < x )
    {
        return containedInSortedarray( std::next( pMiddle ), pEnd, x );
    }
    else
    {
        return true;
    }
}

If you yet do not know iterators then for example this statement

const int *pMiddle = std::next( pBegin, std::distance( pBegin, pEnd ) / 2 );

can be rewritten like

const int *pMiddle = pBegin + ( pEnd - pBegin ) / 2;

and this statement

return containedInSortedarray( std::next( pMiddle ), pEnd, x );

can be rewritten like

return containedInSortedarray( ++pMiddle, pEnd, x );

This DOES work, thank you! Sadly I cannot use this for the assignment but it does give me a clearer picture on how to solve it. I'll give it another try, thanks! — EriPeri, Jan 30 '22 at 18:44

Binary search of an array using recursive function and pointers

1 Answers1