recursive binary search in c++ using a bool function

Question

I have an school assignement that requires me to create a recursive Binary search function. I'm not allowed to change the function signature. My experience with pointer isn't the best and i think my problem lies there. I get an Stackoveflow but i dont really understand way

bool contains(const int* pBegin, const int* pEnd, int x)
{
    int length = pEnd - pBegin;//gives me the length of the array
    const int* pMid = pBegin + (length / 2);
    if(length == 1)
    {
        if(*pMid != x)
           return false;
        return true;
    }
    else if(x < *pMid)
        return contains(pBegin, pMid-1, x);
    else 
        return contains(pMid, pEnd, x);
}

void main(){
    setlocale(LC_ALL, "swedish");
    int arr[10];
    for(int i = 0; i < 10; ++i)
        arr[i] = i;
    bool find = contains(&arr[0], &arr[10], 3);//arr[10] points to the index after the array!
    cout <<"found = "<< find << endl;
    system("pause");
}

Can somebody please explain to me what I'm doing wrong, and how i could do it in a better way?

It sounds like you may need to learn how to use a debugger to step through your code. With a good debugger, you can execute your program line by line and see where it is deviating from what you expect. This is an essential tool if you are going to do any programming. Further reading: How to debug small programs — NathanOliver
– NathanOliver, Commented Jan 19, 2017 at 18:41
I get an Stackoveflow -- Due to probably infinite recursion. You are calling contains, which calls contains, which calls contains, etc. and never getting out of this call chain until the stack overflows. — PaulMcKenzie
– PaulMcKenzie, Commented Jan 19, 2017 at 18:43
If you're using C++ you need to get out of the habit of using int arr[10] and instead use std::vector<int> arr. — tadman
– tadman, Commented Jan 19, 2017 at 18:44
@tadman Why? If you know the size at compile time a naked array is okay. I would prefer std::array but it is not a problem. std::vector is going to require dynamic allocation and there is no reason to pay for that if it is not needed. — NathanOliver
– NathanOliver, Commented Jan 19, 2017 at 18:46

joeking · Accepted Answer · 2017-01-19 19:34:24Z

1

Stack overflow is due to too deep recursion. Its unlikely your array is large enough to really be a problem, so what you have is unbounded recursion ... contains() keeps calling itself and fails to detect this.

Look at how this is possible, and add assertions.

Your code assumes pEnd > pBegin

Your code doesn't handle this possibility.

#include <assert.h>
bool contains( ... )
{
    assert(pBegin > pEnd);
    ...

Now, it will abort if this assumption is incorrect.

There are two possibities for (pEnd > pBegin) being false, namely "<" or "==". What does your code do in these two cases?

Spoiler below..

Length can be zero and isn't handled.

answered Jan 19, 2017 at 19:34

joeking

2,14620 silver badges32 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

recursive binary search in c++ using a bool function

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related