c++ - Why my recursive function doesn't return the right value?

Question

I'm implementing a binary search and the code is below, however, it doesn't print out the right answer buy it prints out correct answer inside the function body, so it makes me really confused.

#include <iostream>
using namespace std;

int research(int a[], int target, int lowIndex, int highIndex)
{
    int finalIndex;
    cout << lowIndex << " " << highIndex << endl;
    int midIndex = (lowIndex + highIndex) / 2;
    if (a[midIndex] == target)
    {
        finalIndex = midIndex;
        cout << "The final index is: " << finalIndex << endl;
    }
    else
    {
        if (a[midIndex] < target)
        {
            research(a, target, midIndex + 1, highIndex);
        }
        else
        {
            research(a, target, lowIndex, midIndex - 1);
        }
    }
    return finalIndex;
}

int main()
{
    int* array = new int[1000];
    for (int i = 0; i < 1000; i++)
    {
        array[i] = i + 1;
    }
    cout << research(array, 234, 0, 999) << endl;
    return 0;
}

The line:

cout << "The final index is: " << finalIndex << endl;

prints out the right final index but the line

cout << research(array, 234, 0, 999) << endl;

doesn't, instead it prints out random number. Anyone know what is going wrong here? Thank you!

Answer 1

The only time you actually set finalIndex to anything is when a[midIndex] == target, so when you recurse you're returning the value of an uninitialised variable.

(The finalIndex variable isn't shared between function invocations - each invocation uses its own variable.)

You need to use the return value from the recursive calls:

    if (a[midIndex] < target)
    {
        finalIndex = research(a, target, midIndex + 1, highIndex);
    }
    else
    {
        finalIndex = research(a, target, lowIndex, midIndex - 1);
    }