Welcome to OStack Knowledge Sharing Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
573 views
in Technique[技术] by (71.8m points)

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

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!

See Question&Answers more detail:os

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Answer

0 votes
by (71.8m points)

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);
    }

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome to OStack Knowledge Sharing Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

...