Cómo implementar la búsqueda lineal mediante recursividad en C, C ++, Python y JavaScript

Aranzulla de Los Pobres

La búsqueda lineal es un algoritmo de búsqueda simple en el que se realiza una búsqueda secuencial de todos los elementos uno por uno. Este algoritmo a menudo se implementa utilizando el enfoque iterativo, pero a veces los entrevistadores modifican el problema y piden implementar el algoritmo de forma recursiva.

En este artículo, aprenderá a implementar el algoritmo de búsqueda lineal mediante la recursividad en C ++, Python, JavaScript y C.

Planteamiento del problema

Se le da una matriz sin clasificar y un elemento para buscar en la matriz dada. Necesita escribir una función recursiva tal que si el elemento se encuentra en la matriz dada, se devuelve el índice del elemento y si el elemento no se encuentra en la matriz, se devuelve -1.

Ejemplo 1 : Sea arr = [1, 2, 3, 4, 5, 6, 7] y elementToBeSearched = 4

4 está presente en la matriz en el índice 3.

Por lo tanto, la función devuelve 3 y el "Elemento 4 encontrado en el índice 3" se muestra en la salida.

Ejemplo 2 : Sea arr = [1, 1, 1, 1, 1] y elementToBeSearched = 2

2 no está presente en la matriz.

Por lo tanto, la función devuelve -1 y en la salida se muestra "Elemento 2 no encontrado".

Enfoque para resolver el problema

  1. Compare el elemento que se buscará con el elemento en el índice más a la izquierda y el índice más a la derecha en la matriz.
  2. Si se encuentra el elemento, devuelve el índice.
  3. De lo contrario, busque recursivamente el elemento para el resto de la matriz incrementando el índice izquierdo y disminuyendo el índice derecho.
  4. Llame a la función de forma recursiva hasta que el índice derecho sea menor que el índice izquierdo.

Relacionado Cómo encontrar la suma de todos los elementos en una matriz

Programa C ++ para implementar el algoritmo de búsqueda lineal mediante recursividad

A continuación se muestra el programa C ++ para implementar el algoritmo de búsqueda lineal mediante recursividad:

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

Producción:

 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

Relacionado: Introducción al algoritmo de clasificación por fusión

Programa Python para implementar el algoritmo de búsqueda lineal mediante recursividad

A continuación se muestra el programa Python para implementar el algoritmo de búsqueda lineal mediante recursividad:

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

Producción:

 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

Relacionado: Cómo encontrar la suma de números naturales usando la recursividad

Programa JavaScript para implementar el algoritmo de búsqueda lineal mediante recursividad

A continuación se muestra el programa JavaScript para implementar el algoritmo de búsqueda lineal mediante recursividad:

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

Producción:

 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

Relacionado: Introducción al algoritmo de clasificación de burbujas

Programa C para implementar el algoritmo de búsqueda lineal mediante recursividad

A continuación se muestra el programa en C para implementar el algoritmo de búsqueda lineal mediante recursividad:

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

Producción:

 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

Aprender recursividad

La recursividad es un tema de programación muy importante y divertido. La recursividad está hecha para resolver problemas que se pueden dividir en problemas más pequeños y repetitivos. Puede ser un poco difícil de aprender para programadores principiantes, pero vale la pena aprender a resolver problemas usando la recursividad.