Recursive binary search function in C++

Question

I'm writing a recursive binary search function for a project in C++ and for some reason, it runs infinitely and does not execute properly. My code is as follows:

int recursiveBin(const int list[], int listLength, int searchItem)
{
    if(listLength == 0)
        return -1;

    int mid = (listLength - 1)/2;

    if(list[mid] > searchItem)
        return recursiveBin(list, mid - 1, searchItem);
    else if(list[mid] < searchItem)
        return recursiveBin(list, mid + 1, searchItem);
    else
        return mid;
}

Can someone please help me with this? I'm not sure what is going wrong with my function and where the infinite loop comes.

Take a piece of paper - create sample input - and write down what happens. Figure out at what point it goes wrong and fix. — Andrew_CS
– Andrew_CS, Commented Jul 18, 2014 at 22:37

bestalign · Accepted Answer · 2014-07-18 22:37:17Z

2

Add one more parameter to store the search boundary.

int recursiveBin(const int list[], int start, int end, int searchItem)
{
    if(end > start)
        return -1;

    int mid = (start + end)/2;

    if(list[mid] > searchItem)
        return recursiveBin(list, start, mid - 1, searchItem);
    else if(list[mid] < searchItem)
        return recursiveBin(list, mid + 1, end, searchItem);
    else
        return mid;
}

answered Jul 18, 2014 at 22:37

bestalign

2271 silver badge9 bronze badges

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

1 Comment

Jonathan Leffler Over a year ago

Or when searching the upper range, pass list + mid + 1 and listLength - mid - 1 as the length parameter.

Collectives™ on Stack Overflow

Recursive binary search function in C++

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related