C++: ошибка выполнения с простой функцией рекурсивного поиска

Question

Итак, у меня есть программа, которая должна выполнить очень простую задачу поиска по массиву из 100 целых чисел, чтобы найти конкретный ключ. Функция linearSearch в этой программе должна быть рекурсивной, поэтому я должен вызвать функцию изнутри. Программа компилируется отлично, но по какой-то причине возвращает только первый элемент 0, в массив независимо от того, какой ключ поиска вы вставляете. Что я не вижу? Благодарю.

#include <iostream> 
using namespace std; 

int linearSearch(const int[], int, int); 

int main() 
{ 
    const int arraySize = 100; //size of array 
    int a[arraySize]; //create array a 
    int searchKey; //value to locate in array a 

    for(int i = 0; i < arraySize; i++) 
      a[i] = 2 * i; //create data 

    cout << "Enter integer search key: "; 
    cin >> searchKey; 

    //attempt to locate search key in array a 
    int element = linearSearch(a, searchKey, arraySize); 

    //display results 
    if(element != -1) 
       cout << "Found value in element: " << element << endl; 
    else 
       cout << "Value not found" << endl; 

    system("pause"); 
} 

//linearSearch Function ****Returns 0 as index all the time ************* 
int linearSearch(const int array[], int key, int sizeOfArray) 
{ 
    static int index = 0; 

    //if Out of range, return -1 (Value not found) 
    if(index >= sizeOfArray){return -1;} 

    //if array value = key, array index is returned 
    if(array[index] == key){return index;} 

    //if array value is not equal to key, add to index and call func again     
    if(array[index] != key) 
    { 
        index++; 
        linearSearch(array, key, sizeOfArray);     
    } 
} 

Я беру правильный подход, объявляя index как static, верно?

~ Большое спасибо, вы, ребята, быстро и ОГРОМНАЯ помощь. =)

Answer 1

Вы также можете изменить свою функцию поиска без использования статической локальной переменной index.

int linearSearch(const int array[], int index, int key, int sizeOfArray) 
{ 
    //if Out of range, return -1 (Value not found) 
    if(index >= sizeOfArray){return -1;} 

    //if array value = key, array index is returned 
    if(array[index] == key){return index;} 

    //if array value is not equal to key, add to index and call func again     
    return linearSearch(array, index + 1, key, sizeOfArray);     
} 

Единственное изменение заключается в том, что вы передаете начальный индекс в функцию поиска.

Answer 2

Я принимаю правильный подход, объявив index, как static, верно?

Нет. Скорее index должен быть аргументом для рекурсивной функции.

Из-за состояния static эта функция трудно проверить и не является потокобезопасной. Кроме того, он непреднамеренно удерживает состояние между вызовами, а это означает, что если вы должны были его назвать во второй раз, это не сработало бы (поскольку index все равно будет иметь старое значение).

Answer 3

Ваша ошибка состоит в том, что

if(array[index] != key) 
{ 
    index++; 
    linearSearch(array, key, sizeOfArray);     
} 

должен быть

if(array[index] != key) 
{ 
    index++; 
    return linearSearch(array, key, sizeOfArray);     
} 

Вы не возвращает никакого значения, когда ключ не совпадает.

Плюс статический индекс плохой, как уже было сказано.

Answer 4

При повторном поиске этого типа вы должны распространять индекс, который вы сейчас используете в своем массиве.

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

Индекс должен скорее быть параметром, и каждый раз, когда вы вызываете функцию рекурсивно, вы передаете индекс + 1 в качестве параметра.

Кроме того, вы должны вернуть значение рекурсивных вызовов, иначе оно просто ничего не делает и не сохраняет/обрабатывает возвращаемое значение.