Рекурсивный линейный поиск массива

Рекурсивная лестница, иллюстрация рекурсии

Что такое линейный поиск

Линейный поиск (linear search) — простой алгоритм поиска элемента в неотсортированном массиве, при котором элементы проверяются последовательно один за другим. В варианте, разобранном здесь, проверяются одновременно левый и правый элементы, а затем рекурсивно сужается диапазон.

Короткое определение: рекурсивная функция возвращает индекс найденного элемента или -1, если элемент отсутствует.

Постановка задачи

Дан неотсортированный массив и значение для поиска. Напишите рекурсивную функцию, которая вернёт индекс первого найденного совпадения (либо одно из совпадений при двухстороннем обходе) или -1, если элемент не найден.

Примеры

arr = [1, 2, 3, 4, 5, 6, 7], элемент = 4 → возвращается 3
arr = [1, 1, 1, 1, 1], элемент = 2 → возвращается -1

Подход (алгоритм)

Если правый индекс меньше левого, завершить и вернуть -1.
Сравнить элемент слева с искомым.
Сравнить элемент справа с искомым.
Если совпадение найдено — вернуть соответствующий индекс.
Иначе рекурсивно вызвать функцию с left+1 и right-1.
Повторять до тех пор, пока диапазон не исчерпается.

Этот вариант уменьшает количество рекурсивных шагов примерно в два раза по сравнению с однонаправленным обходом: глубина рекурсии ≈ ceil(n/2).

Сложность

Время (в худшем и среднем): O(n) — нужно посетить потенциально все элементы.
Примерное число рекурсивных вызовов: примерно n/2 при двухстороннем обходе.
Память: O(n) в смысле стека вызовов (точнее O(n/2) вызовов), поэтому при больших n возможен переполнение стека.

Важно: рекурсивная версия удобна для упражнений и интервью, но для практических задач с большими массивами предпочтительнее итеративная реализация.

C++ — реализация рекурсивного линейного поиска

// C++: рекурсивный поиск элемента в массиве
#include 
using namespace std;

// Возвращает индекс элемента или -1
int recursiveSearch(int arr[], int left, int right, int elementToBeSearched) {
    if (right < left) {
        return -1;
    }
    if (arr[left] == elementToBeSearched) {
        return left;
    }
    if (arr[right] == elementToBeSearched) {
        return right;
    }
    return recursiveSearch(arr, left + 1, right - 1, elementToBeSearched);
}

void printArrayElements(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
}

int main() {
    int arr1[] = {1, 2, 3, 4, 5, 6, 7};
    int size1 = sizeof(arr1) / sizeof(arr1[0]);
    cout << "Массив 1:" << endl;
    printArrayElements(arr1, size1);
    int elementToBeSearched1 = 4;
    cout << "Искомый элемент: " << elementToBeSearched1 << endl;
    int indexOfElement1 = recursiveSearch(arr1, 0, size1 - 1, elementToBeSearched1);
    if (indexOfElement1 == -1) {
        cout << "Элемент " << elementToBeSearched1 << " не найден" << endl;
    } else {
        cout << "Элемент " << elementToBeSearched1 << " найден на индексе " << indexOfElement1 << endl;
    }

    int arr2[] = {2, 4, 6, 10, 12, 3, 6};
    int size2 = sizeof(arr2) / sizeof(arr2[0]);
    cout << "Массив 2:" << endl;
    printArrayElements(arr2, size2);
    int elementToBeSearched2 = 4;
    cout << "Искомый элемент: " << elementToBeSearched2 << endl;
    int indexOfElement2 = recursiveSearch(arr2, 0, size2 - 1, elementToBeSearched2);
    if (indexOfElement2 == -1) {
        cout << "Элемент " << elementToBeSearched2 << " не найден" << endl;
    } else {
        cout << "Элемент " << elementToBeSearched2 << " найден на индексе " << indexOfElement2 << endl;
    }

    int arr3[] = {1, 1, 1, 1, 1};
    int size3 = sizeof(arr3) / sizeof(arr3[0]);
    cout << "Массив 3:" << endl;
    printArrayElements(arr3, size3);
    int elementToBeSearched3 = 2;
    cout << "Искомый элемент: " << elementToBeSearched3 << endl;
    int indexOfElement3 = recursiveSearch(arr3, 0, size3 - 1, elementToBeSearched3);
    if (indexOfElement3 == -1) {
        cout << "Элемент " << elementToBeSearched3 << " не найден" << endl;
    } else {
        cout << "Элемент " << elementToBeSearched3 << " найден на индексе " << indexOfElement3 << endl;
    }

    return 0;
}

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

Python — реализация

# Python: рекурсивный поиск элемента в списке

def recursiveSearch(arr, left, right, elementToBeSearched):
    if right < left:
        return -1
    if arr[left] == elementToBeSearched:
        return left
    if arr[right] == elementToBeSearched:
        return right
    return recursiveSearch(arr, left + 1, right - 1, elementToBeSearched)


def printListElements(arr):
    print(' '.join(map(str, arr)))

arr1 = [1, 2, 3, 4, 5, 6, 7]
print('Массив 1:')
printListElements(arr1)
elementToBeSearched1 = 4
print('Искомый элемент:', elementToBeSearched1)
indexOfElement1 = recursiveSearch(arr1, 0, len(arr1) - 1, elementToBeSearched1)
if indexOfElement1 == -1:
    print(f'Элемент {elementToBeSearched1} не найден')
else:
    print(f'Элемент {elementToBeSearched1} найден на индексе {indexOfElement1}')

# Повторите аналогичные проверки для других массивов по примеру C++

JavaScript — реализация

// JavaScript: рекурсивный поиск элемента в массиве
function recursiveSearch(arr, left, right, elementToBeSearched) {
  if (right < left) {
    return -1;
  }
  if (arr[left] === elementToBeSearched) {
    return left;
  }
  if (arr[right] === elementToBeSearched) {
    return right;
  }
  return recursiveSearch(arr, left + 1, right - 1, elementToBeSearched);
}

function printArrayElements(arr) {
  console.log(arr.join(' '));
}

let arr1 = [1, 2, 3, 4, 5, 6, 7];
console.log('Массив 1:');
printArrayElements(arr1);
let elementToBeSearched1 = 4;
console.log('Искомый элемент:', elementToBeSearched1);
let indexOfElement1 = recursiveSearch(arr1, 0, arr1.length - 1, elementToBeSearched1);
if (indexOfElement1 === -1) {
  console.log(`Элемент ${elementToBeSearched1} не найден`);
} else {
  console.log(`Элемент ${elementToBeSearched1} найден на индексе ${indexOfElement1}`);
}

C — реализация

// C: рекурсивный поиск элемента в массиве
#include 

int recursiveSearch(int arr[], int left, int right, int elementToBeSearched) {
    if (right < left) {
        return -1;
    }
    if (arr[left] == elementToBeSearched) {
        return left;
    }
    if (arr[right] == elementToBeSearched) {
        return right;
    }
    return recursiveSearch(arr, left + 1, right - 1, elementToBeSearched);
}

void printArrayElements(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

int main() {
    int arr1[] = {1, 2, 3, 4, 5, 6, 7};
    int size1 = sizeof(arr1) / sizeof(arr1[0]);
    printf("Массив 1:\n");
    printArrayElements(arr1, size1);
    int elementToBeSearched1 = 4;
    printf("Искомый элемент: %d\n", elementToBeSearched1);
    int indexOfElement1 = recursiveSearch(arr1, 0, size1 - 1, elementToBeSearched1);
    if (indexOfElement1 == -1) {
        printf("Элемент %d не найден\n", elementToBeSearched1);
    } else {
        printf("Элемент %d найден на индексе %d\n", elementToBeSearched1, indexOfElement1);
    }
    return 0;
}

Когда этот подход не подходит

Очень большие массивы: рекурсивная реализация может привести к переполнению стека. Используйте итеративный вариант.
Когда нужен гарантированный минимальный расход памяти: рекурсивный стек увеличивает потребление памяти.
Если данные отсортированы и требуется частый поиск — лучше бинарный поиск (O(log n)) или структура данных (хэш-таблица) для O(1) амортизированного доступа.

Критерии приёмки

Функция возвращает индекс одного из вхождений искомого элемента в пределах [left, right] либо -1, если нет совпадений.
Для пустого массива (left > right) возвращается -1.
Для массивов с одним элементом корректно определяется присутствие/отсутствие.
Для массивов с парой совпадений возвращается индекс либо левого, либо правого совпадения (в зависимости от порядка проверок).

Тестовые случаи (минимум)

Пустой массив → -1
Массив из одного элемента, элемент найден/не найден
Элемент в начале, середине, в конце
Повторяющиеся элементы — убедиться, что возвращаемый индекс соответствует одному из повторов
Большой массив (ключевой тест на стек/память)

Шаблон для интервью: чеклист кандидата

Поясните сложность O(n) и причину глубины рекурсии.
Укажите граничные случаи (пустой массив, один элемент).
Предложите итеративную реализацию как альтернативу.
Объясните, когда лучше использовать другие алгоритмы (бинарный поиск, хеширование).

Небольшая методология выбора подхода

Нужна читаемость и короткий код (учебная/интервью): рекурсивный вариант приемлем.
Нужна производительность и стабильность при больших входных данных: итеративный вариант или структуры данных.

Факт-бокс: ключевые числа

Худшая глубина рекурсии: ≈ n/2 вызовов (при двухстороннем обходе).
Время: O(n).
Память (стек): O(n) асимптотически (точнее O(n/2)).

Быстрый мермайд-диаграмма (логика поиска)

flowchart TD
  Start'[Start]' --> CheckEmpty{right < left?}
  CheckEmpty -- Yes --> NotFound['Вернуть -1']
  CheckEmpty -- No --> CompareLeft{arr[left] == x?}
  CompareLeft -- Yes --> FoundLeft['Вернуть left']
  CompareLeft -- No --> CompareRight{arr[right] == x?}
  CompareRight -- Yes --> FoundRight['Вернуть right']
  CompareRight -- No --> Recurse['left+1, right-1']
  Recurse --> CheckEmpty

Итог

Рекурсивный линейный поиск — хороший учебный пример рекурсии и полезный инструмент в интервью. В практических задачах, где важна эффективность по памяти или гарантированная устойчивость на больших входных данных, лучше выбирать итеративные решения или специализированные структуры данных.