Рекурсивный линейный поиск — примеры на C++/Python/JS/C

рекурсивная лестница, иллюстрация рекурсивного вызова функций

Linear search — простой алгоритм поиска, при котором перебирают элементы по очереди. Часто его реализуют итеративно, но на собеседованиях иногда просят реализовать рекурсивную версию.

Задача

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

Примеры:

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

Подход

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

Понимание в одну фразу: это двухуказательный (two-pointer) подход с рекурсией, где область поиска сужается с обеих сторон.

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

Ниже — исходная программа на C++:

// C++ program to recursively search an element in an array  
#include   
using namespace std;  
  
// Function to recursively search an element in an array  
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

Вывод программы:

Array 1:  
1 2 3 4 5 6 7  
Element to be searched: 4  
Element 4 found at index 3  
Array 2:  
2 4 6 10 12 3 6  
Element to be searched: 4  
Element 4 found at index 1  
Array 3:  
1 1 1 1 1  
Element to be searched: 2  
Element 2 not found

`Python: реализация рекурсивного линейного поиска`

Исходный код на Python:

# Python program to recursively search an element in an array  
  
# Function to recursively search an element in an arrays  
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, size):  
    for i in range(size):  
        print(arr[i], end=" ")  
    print()  
  
arr1 = [1, 2, 3, 4, 5, 6, 7]  
size1 = len(arr1)  
print("Array 1:")  
printListElements(arr1, size1)  
elementToBeSearched1 = 4  
print("Element to be searched:", elementToBeSearched1)  
indexOfElement1 = recursiveSearch(arr1, 0, size1-1, elementToBeSearched1)  
if indexOfElement1 == -1:  
    print("Element", elementToBeSearched1, "not found")  
else:  
    print("Element", elementToBeSearched1, "found at index", indexOfElement1)  
arr2 = [2, 4, 6, 10, 12, 3, 6]  
size2 = len(arr2)  
print("Array 2:")  
printListElements(arr2, size2)  
elementToBeSearched2 = 4  
print("Element to be searched:", elementToBeSearched2)  
indexOfElement2 = recursiveSearch(arr2, 0, size2-1, elementToBeSearched2)  
if indexOfElement2 == -1:  
    print("Element", elementToBeSearched2, "not found")  
else:  
    print("Element", elementToBeSearched2, "found at index", indexOfElement2)  
arr3 = [1, 1, 1, 1, 1]  
size3 = len(arr3)  
print("Array 3:")  
printListElements(arr3, size3)  
elementToBeSearched3 = 2  
print("Element to be searched:", elementToBeSearched3)  
indexOfElement3 = recursiveSearch(arr3, 0, size3-1, elementToBeSearched3)  
if indexOfElement3 == -1:  
    print("Element", elementToBeSearched3, "not found")  
else:  
    print("Element", elementToBeSearched3, "found at index", indexOfElement3)

Вывод тот же, что в примерах выше.

`JavaScript: реализация рекурсивного линейного поиска`

Исходный код на JavaScript:

// JavaScript program to recursively search an element in an array  
  
// Function to recursively search an element in an array  
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, size) {  
 for(let i=0; i

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

Исходный код на C:

// C program to recursively search an element in an array  
#include   
  
// Function to recursively search an element in an array  
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

`Сложность и память`

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

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

`Когда этот подход не подходит (контрпримеры)`

Очень длинные массивы (риск переполнения стека).
Если необходима стабильность по порядку или специфическое правило выбора при дубликатах (например, всегда возвращать первый вхождение) — реализация должна учитывать это явно.
Для отсортированных массивов рекурсивный линейный поиск уступает по эффективности бинарному поиску O(log n).

`Альтернативные подходы`

Итеративный линейный поиск — проще и безопаснее по памяти.
std::find в C++ или .index() в Python — готовые реализации.
Бинарный поиск для отсортированных массивов.

`Ментальная модель`

Представьте массив как коридор с двух сторон: вы стоите посередине и проверяете двери слева и справа, постепенно двигаясь к центру.

`Контрольные примеры и критерии приёмки`

Тест 1: [1,2,3,4,5], 4 → индекс 3.
Тест 2: [2,4,6,10,12,3,6], 4 → индекс 1.
Тест 3: [1,1,1,1], 1 → индекс 0 (левый край приоритетен).
Тест 4: [], 5 → -1.
Тест 5: [5], 5 → 0.

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

Функция возвращает корректный индекс для всех тестов выше.
Возвращает -1, если элемент отсутствует.
Не ломается на пустых массивах.

`Чеклист для собеседования`

Объясните выбранный подход (two-pointer + рекурсия).
Назовите временную и пространственную сложность.
Укажите, как обрабатывать дубликаты.
Обсудите ограничения рекурсии и альтернативы.

`Короткий словарь`

Рекурсия — функция, которая вызывает сама себя.
Стек вызовов — структура, где хранятся активные вызовы функций.
Линейный поиск — последовательный перебор элементов для поиска совпадения.
Два указателя — приём, где два индекса сдвигают границы области поиска.

`Итог`

Рекурсивный линейный поиск — удобный образовательный пример для практики рекурсии и понимания двухуказательного подхода. Для реальных задач на больших данных предпочтительнее итеративные варианты или специализированные алгоритмы (например, бинарный поиск для отсортированных массивов).

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