Comment implémenter la recherche linéaire à l’aide de la récursivité en C, C++, Python et JavaScript

Hibou Gourou

La recherche linéaire est un algorithme de recherche simple dans lequel une recherche séquentielle est effectuée sur tous les éléments un par un. Cet algorithme est souvent implémenté en utilisant l'approche itérative, mais parfois les enquêteurs peaufinent le problème et demandent d'implémenter l'algorithme de manière récursive.

Dans cet article, vous apprendrez à implémenter l'algorithme de recherche linéaire à l'aide de la récursivité en C++, Python, JavaScript et C.

Énoncé du problème

On vous donne un tableau non trié et un élément à rechercher dans le tableau donné. Vous devez écrire une fonction récursive telle que si l'élément est trouvé dans le tableau donné, l'indice de l'élément est renvoyé et si l'élément n'est pas trouvé dans le tableau, -1 est renvoyé.

Exemple 1 : Soit arr = [1, 2, 3, 4, 5, 6, 7] et elementToBeSearched = 4

4 est présent dans le tableau à l'index 3.

Ainsi, 3 est renvoyé de la fonction et "Élément 4 trouvé à l'index 3" est affiché sur la sortie.

Exemple 2 : Soit arr = [1, 1, 1, 1, 1] et elementToBeSearched = 2

2 n'est pas présent dans le tableau.

Ainsi, -1 est renvoyé par la fonction et "Element 2 not found" est affiché sur la sortie.

Approche pour résoudre le problème

  1. Comparez l'élément à rechercher avec l'élément à l'index le plus à gauche et à l'index le plus à droite dans le tableau.
  2. Si l'élément est trouvé, retourne l'index.
  3. Sinon, recherchez récursivement l'élément pour le reste du tableau en incrémentant l'index de gauche et en décrémentant l'index de droite.
  4. Appelez la fonction de manière récursive jusqu'à ce que l'index de droite soit inférieur à l'index de gauche.

Connexe: Comment trouver la somme de tous les éléments d'un tableau

Programme C++ pour implémenter l'algorithme de recherche linéaire à l'aide de la récursivité

Vous trouverez ci-dessous le programme C++ pour implémenter l'algorithme de recherche linéaire en utilisant la récursivité :

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

Production:

 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

Connexes : Introduction à l'algorithme de tri par fusion

Programme Python pour implémenter l'algorithme de recherche linéaire à l'aide de la récursivité

Vous trouverez ci-dessous le programme Python pour implémenter l'algorithme de recherche linéaire à l'aide de la récursivité :

 # 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)

Production:

 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

Connexes : Comment trouver la somme des nombres naturels à l'aide de la récursivité

Programme JavaScript pour implémenter l'algorithme de recherche linéaire à l'aide de la récursivité

Vous trouverez ci-dessous le programme JavaScript pour implémenter l'algorithme de recherche linéaire à l'aide de la récursivité :

 // 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>");
 }

Production:

 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

Connexes : Introduction à l'algorithme de tri à bulles

Programme C pour implémenter l'algorithme de recherche linéaire en utilisant la récursivité

Vous trouverez ci-dessous le programme C pour implémenter l'algorithme de recherche linéaire en utilisant la récursivité :

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

Production:

 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

Apprendre la récursivité

La récursivité est un sujet de programmation très important et amusant. La récursivité est conçue pour résoudre des problèmes qui peuvent être décomposés en problèmes plus petits et répétitifs. Cela peut être un peu difficile à apprendre pour les programmeurs débutants, mais apprendre à résoudre des problèmes en utilisant la récursivité en vaut la peine.