Understanding a recursive Binary Search Algorithm that mysteriously works

Question

On an assignment I had to make a recursive binary search algorithm output the index instead of True/False without modifying the parameters. I had a really tough time but after resorting to semi-trial-and-error I stumbled upon this mess:

#include <iostream>
#include <math.h>
#include <climits>

using namespace std;


int BinarySearch(int arr[], int len, int target) {

    int temp = 0;
    int mid = len/2;

    if (len <= 0) return INT_MIN;  // not found
    if (target == arr[mid]){
        return mid; // found
    }

    if (target < arr[mid]){
        temp = BinarySearch(arr, mid, target);
    }

    else {
        temp = mid+1 + BinarySearch(arr+mid+1, len-mid-1, target);              
    }
}

I have literally no idea why it works, even after running it through a visualizer. It's very sensitive to the code being changed and I can't get it to output -1 when it fails to find the target so I made it at least always output a negative number instead.

I don't really need it fixed, I just want to know how it even works since seemingly none of the recursive call's outputs are even used. Thanks.

Try to [explain it to your rubber duck](https://en.wikipedia.org/wiki/Rubber_duck_debugging). Or step through it line by line (stepping into the recursive calls) with a debugger. Both ways are good to find a very big bug, that leads to *undefined behavior*. — Some programmer dude, Feb 27 '18 at 07:44
`INT_MIN` as a "not found" is kinda bad. It's a perfectly valid integer value. — StoryTeller - Unslander Monica, Feb 27 '18 at 07:55

score 5 · Answer 1 · answered Feb 27 '18 at 08:16

It is undefined behaviour (see e.g. Why does flowing off the end of a non-void function without returning a value not produce a compiler error?).

The compiler appears to return temp by chance, likely because it is the first local variable declared inside the function. Returning temp would fix it.

Thomas Sablik · Answer 2 · 2018-03-01T10:57:59.060

0

As far as I understand you want to return -1, if the target is not found and the index of the target otherwise. In

if (len <= 0) return INT_MIN;  // not found

you are returning INT_MIN, if the target is not found. You need to change it to

if (len <= 0) return -1;  // not found

Since your function returns an int value, it has to return something on each patch. You can fix it by adding the return at the end of the function:

    if (target < arr[mid]){
        temp = BinarySearch(arr, mid, target);
    }

    else {
        temp = mid+1 + BinarySearch(arr+mid+1, len-mid-1, target);              
    }
    return temp;
}

BinarySearch returns the index of target in the current arr. Since the current arr often doesn't begin with index 0, you're adding and subtracting mid+1. You're also doing it, if the target was not found and BinarySearch returns -1. You have to fix the else part:

else {
    int index(BinarySearch(arr+mid+1, len-mid-1, target));
    temp = index == -1 ? -1 : mid + 1 + index;              
}

edited Mar 01 '18 at 10:57

answered Feb 27 '18 at 08:42

Thomas Sablik

16,127
7
34
62

Ah okay, it was returning `temp` after all. The problem still persists with returning -1 if not found though. It seems to add whatever number I want to return in `if (len <= 0) return x;`, and I can't figure out a way to make it -1 each time (since `temp` contains the index, which changes). – Leo Steeves Feb 28 '18 at 21:17
I've found another mistake and edited my answer. – Thomas Sablik Mar 01 '18 at 10:59
Ah ha! That works, thanks you. I don't understand what the line `int index(BinarySearch(arr+mid+1, len-mid-1, target));` does though. Is it a function or just a way of declaring a variable I've never seen before? – Leo Steeves Mar 02 '18 at 20:34
It's the `c++` way of `int index = BinarySearch(arr+mid+1, len-mid-1, target);` – Thomas Sablik Mar 02 '18 at 23:27

Understanding a recursive Binary Search Algorithm that mysteriously works

2 Answers2