Почему моя рекурсивная функция не возвращает правильное значение?

Question

Я реализую двоичный поиск, а код ниже, однако он не распечатывает правильный ответ. Купите его, чтобы напечатать правильный ответ внутри тела функции, поэтому он меня очень смущает.

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

Линия:

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

печатает правой конечного индекса, но линии

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

не делает, вместо этого он выводит случайное число. Кто-нибудь знает, что здесь происходит не так? Спасибо!

Answer 1

Единственный раз, когда вы на самом деле установили finalIndex на что-либо, когда a[midIndex] == target, поэтому, когда вы рекурсируете, вы возвращаете значение неинициализированной переменной.

(переменная finalIndex не разделяется между функциональными вызовами - каждый вызов использует свою собственную переменную.)

Вы должны использовать возвращаемое значение из рекурсивных вызовов:

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