So implementieren Sie eine lineare Suche mit Rekursion in C, C++, Python und JavaScript

Eskere Guru

Die lineare Suche ist ein einfacher Suchalgorithmus, bei dem eine sequentielle Suche über alle Elemente nacheinander durchgeführt wird. Dieser Algorithmus wird oft mit dem iterativen Ansatz implementiert, aber manchmal optimieren die Interviewer das Problem und bitten darum, den Algorithmus rekursiv zu implementieren.

In diesem Artikel erfahren Sie, wie Sie den linearen Suchalgorithmus mithilfe von Rekursion in C++, Python, JavaScript und C implementieren.

Problemstellung

Sie erhalten ein unsortiertes Array und ein zu suchendes Element im angegebenen Array. Sie müssen eine rekursive Funktion schreiben, sodass, wenn das Element im angegebenen Array gefunden wird, der Index des Elements zurückgegeben wird und wenn das Element nicht im Array gefunden wird, -1 zurückgegeben wird.

Beispiel 1 : Sei arr = [1, 2, 3, 4, 5, 6, 7] und elementToBeSearched = 4

4 ist im Array an Index 3 vorhanden.

Somit wird 3 von der Funktion zurückgegeben und am Ausgang wird "Element 4 gefunden bei Index 3" angezeigt.

Beispiel 2 : Sei arr = [1, 1, 1, 1, 1] und elementToBeSearched = 2

2 ist im Array nicht vorhanden.

Somit wird -1 von der Funktion zurückgegeben und am Ausgang wird "Element 2 not found" angezeigt.

Ansatz zur Lösung des Problems

  1. Vergleichen Sie das zu suchende Element mit dem Element am linken Index und am rechten Index im Array.
  2. Wenn das Element gefunden wird, geben Sie den Index zurück.
  3. Sonst durchsuchen Sie das Element rekursiv nach dem Rest des Arrays, indem Sie den linken Index inkrementieren und den rechten Index dekrementieren.
  4. Rufen Sie die Funktion rekursiv auf, bis der rechte Index kleiner als der linke Index ist.

Verwandte: So finden Sie die Summe aller Elemente in einem Array

C++-Programm zur Implementierung des linearen Suchalgorithmus mit Rekursion

Unten ist das C++-Programm zum Implementieren des linearen Suchalgorithmus mit Rekursion:

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

Ausgabe:

 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

Verwandte: Eine Einführung in den Merge-Sortieralgorithmus

Python-Programm zur Implementierung des linearen Suchalgorithmus mit Rekursion

Unten ist das Python-Programm zum Implementieren des linearen Suchalgorithmus mit Rekursion:

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

Ausgabe:

 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

Verwandte: So finden Sie die Summe natürlicher Zahlen mit Rekursion

JavaScript-Programm zur Implementierung des linearen Suchalgorithmus mit Rekursion

Unten ist das JavaScript-Programm zum Implementieren des linearen Suchalgorithmus mit Rekursion:

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

Ausgabe:

 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

Verwandte: Eine Einführung in den Bubble-Sort-Algorithmus

C-Programm zur Implementierung des linearen Suchalgorithmus mit Rekursion

Unten ist das C-Programm zur Implementierung des linearen Suchalgorithmus mit Rekursion:

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

Ausgabe:

 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

Rekursion lernen

Rekursion ist ein sehr wichtiges und unterhaltsames Programmierthema. Rekursion dient der Lösung von Problemen, die in kleinere, sich wiederholende Probleme zerlegt werden können. Es mag für Programmieranfänger etwas schwierig sein, es zu lernen, aber es lohnt sich zu lernen, wie man Probleme mit Rekursion löst.