Как реализовать линейный поиск с помощью рекурсии в C, C ++, Python и JavaScript

Дядя Влад

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

В этой статье вы узнаете, как реализовать алгоритм линейного поиска с использованием рекурсии в C ++, Python, JavaScript и C.

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

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

Пример 1. Пусть arr = [1, 2, 3, 4, 5, 6, 7] и elementToBeSearched = 4

4 присутствует в массиве с индексом 3.

Таким образом, функция возвращает 3, а на выходе отображается «Элемент 4, найденный в индексе 3».

Пример 2. Пусть arr = [1, 1, 1, 1, 1] и elementToBeSearched = 2

2 нет в массиве.

Таким образом, функция возвращает -1, а на выходе отображается «Элемент 2 не найден».

Подход к решению проблемы

  1. Сравните искомый элемент с крайним левым индексом и крайним правым индексом в массиве.
  2. Если элемент найден, верните индекс.
  3. Иначе рекурсивно ищите элемент для остальной части массива, увеличивая левый индекс и уменьшая правый индекс.
  4. Вызывайте функцию рекурсивно, пока правый индекс не станет меньше левого индекса.

Связанный: Как найти сумму всех элементов в массиве

Программа на C ++ для реализации алгоритма линейного поиска с использованием рекурсии

Ниже представлена ​​программа на C ++ для реализации алгоритма линейного поиска с использованием рекурсии:

 // C++ program to recursively search an element in an array
 #include <iostream>
 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<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 << "Array 1:" << endl;
 printArrayElements(arr1, size1);
 int elementToBeSearched1 = 4;
 cout << "Element to be searched: " << elementToBeSearched1 << endl;
 int indexOfElement1 = recursiveSearch(arr1, 0, size1-1, elementToBeSearched1);
 if(indexOfElement1 == -1)
 {
 cout << "Element " << elementToBeSearched1 << " not found" << endl;
 }
 else
 {
 cout << "Element " << elementToBeSearched1 << " found at index " << indexOfElement1 << endl;
 }
 int arr2[] = {2, 4, 6, 10, 12, 3, 6};
 int size2 = sizeof(arr2)/sizeof(arr2[0]);
 cout << "Array 2:" << endl;
 printArrayElements(arr2, size2);
 int elementToBeSearched2 = 4;
 cout << "Element to be searched: " << elementToBeSearched2 << endl;
 int indexOfElement2 = recursiveSearch(arr2, 0, size2-1, elementToBeSearched2);
 if(indexOfElement2 == -1)
 {
 cout << "Element " << elementToBeSearched2 << " not found" << endl;
 }
 else
 {
 cout << "Element " << elementToBeSearched2 << " found at index " << indexOfElement2 << endl;
 }
 int arr3[] = {1, 1, 1, 1, 1};
 int size3 = sizeof(arr3)/sizeof(arr3[0]);
 cout << "Array 3:" << endl;
 printArrayElements(arr3, size3);
 int elementToBeSearched3 = 2;
 cout << "Element to be searched: " << elementToBeSearched3 << endl;
 int indexOfElement3 = recursiveSearch(arr3, 0, size3-1, elementToBeSearched3);
 if(indexOfElement3 == -1)
 {
 cout << "Element " << elementToBeSearched3 << " not found" << endl;
 }
 else
 {
 cout << "Element " << elementToBeSearched3 << " found at index " << indexOfElement3 << endl;
 }
 return 0;
 }

Выход:

 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)

Выход:

 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

Связанный: Как найти сумму натуральных чисел с помощью рекурсии

Программа на 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<size; i++) {
 document.write(arr[i] + " ");
 }
 document.write("<br>");
 }
 var arr1 = [1, 2, 3, 4, 5, 6, 7];
 var size1 = arr1.length;
 document.write("Array 1:" + "<br>");
 printArrayElements(arr1, size1);
 var elementToBeSearched1 = 4;
 document.write("Element to be searched: " + elementToBeSearched1 + "<br>");
 var indexOfElement1 = recursiveSearch(arr1, 0, size1-1, elementToBeSearched1);
 if(indexOfElement1 == -1) {
 document.write("Element " + elementToBeSearched1 + " not found" + "<br>");
 } else {
 document.write("Element " + elementToBeSearched1 + " found at index " + indexOfElement1 + "<br>");
 }
 var arr2 = [2, 4, 6, 10, 12, 3, 6];
 var size2 = arr2.length;
 document.write("Array 2:" + "<br>");
 printArrayElements(arr2, size2);
 var elementToBeSearched2 = 4;
 document.write("Element to be searched: " + elementToBeSearched2 + "<br>");
 var indexOfElement2 = recursiveSearch(arr2, 0, size2-1, elementToBeSearched2);
 if(indexOfElement2 == -1) {
 document.write("Element " + elementToBeSearched2 + " not found" + "<br>");
 } else {
 document.write("Element " + elementToBeSearched2 + " found at index " + indexOfElement2 + "<br>");
 }
 var arr3 = [1, 1, 1, 1, 1];
 var size3 = arr3.length;
 document.write("Array 3:" + "<br>");
 printArrayElements(arr3, size3);
 var elementToBeSearched3 = 2;
 document.write("Element to be searched: " + elementToBeSearched3 + "<br>");
 var indexOfElement3 = recursiveSearch(arr3, 0, size3-1, elementToBeSearched3);
 if(indexOfElement3 == -1) {
 document.write("Element " + elementToBeSearched3 + " not found" + "<br>");
 } else {
 document.write("Element " + elementToBeSearched3 + " found at index " + indexOfElement3 + "<br>");
 }

Выход:

 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

Связанный: Введение в алгоритм пузырьковой сортировки

Программа на C для реализации алгоритма линейного поиска с использованием рекурсии

Ниже представлена ​​программа на языке C для реализации алгоритма линейного поиска с использованием рекурсии:

 // C program to recursively search an element in an array
 #include <stdio.h>
 // 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<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("Array 1: ⁠n");
 printArrayElements(arr1, size1);
 int elementToBeSearched1 = 4;
 printf("Element to be searched: %d ⁠n", elementToBeSearched1);
 int indexOfElement1 = recursiveSearch(arr1, 0, size1-1, elementToBeSearched1);
 if(indexOfElement1 == -1)
 {
 printf("Element %d not found ⁠n", elementToBeSearched1);
 }
 else
 {
 printf("Element %d found at index %d ⁠n", elementToBeSearched1, indexOfElement1);
 }
 int arr2[] = {2, 4, 6, 10, 12, 3, 6};
 int size2 = sizeof(arr2)/sizeof(arr2[0]);
 printf("Array 2: ⁠n");
 printArrayElements(arr2, size2);
 int elementToBeSearched2 = 4;
 printf("Element to be searched: %d ⁠n", elementToBeSearched2);
 int indexOfElement2 = recursiveSearch(arr2, 0, size2-1, elementToBeSearched2);
 if(indexOfElement2 == -1)
 {
 printf("Element %d not found ⁠n", elementToBeSearched2);
 }
 else
 {
 printf("Element %d found at index %d ⁠n", elementToBeSearched2, indexOfElement2);
 }
 int arr3[] = {1, 1, 1, 1, 1};
 int size3 = sizeof(arr3)/sizeof(arr3[0]);
 printf("Array 3: ⁠n");
 printArrayElements(arr3, size3);
 int elementToBeSearched3 = 2;
 printf("Element to be searched: %d ⁠n", elementToBeSearched3);
 int indexOfElement3 = recursiveSearch(arr3, 0, size3-1, elementToBeSearched3);
 if(indexOfElement3 == -1)
 {
 printf("Element %d not found ⁠n", elementToBeSearched3);
 }
 else
 {
 printf("Element %d found at index %d ⁠n", elementToBeSearched3, indexOfElement3);
 }
 return 0;
 }

Выход:

 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

Изучите рекурсию

Рекурсия – очень важная и интересная тема программирования. Рекурсия предназначена для решения проблем, которые можно разбить на более мелкие повторяющиеся проблемы. Начинающим программистам может быть немного сложно научиться этому, но научиться решать проблемы с помощью рекурсии того стоит.