Como implementar pesquisa linear usando recursão em C, C ++, Python e JavaScript

gurinho

A pesquisa linear é um algoritmo de pesquisa simples no qual uma pesquisa sequencial é feita em todos os itens, um por um. Este algoritmo é frequentemente implementado usando a abordagem iterativa, mas às vezes os entrevistadores ajustam o problema e pedem para implementar o algoritmo recursivamente.

Neste artigo, você aprenderá como implementar o algoritmo de pesquisa linear usando recursão em C ++, Python, JavaScript e C.

Declaração do Problema

Você recebe uma matriz não classificada e um elemento a ser pesquisado na matriz fornecida. Você precisa escrever uma função recursiva de forma que, se o elemento for encontrado no array fornecido, o índice do elemento seja retornado e se o elemento não for encontrado no array, -1 seja retornado.

Exemplo 1 : Let arr = [1, 2, 3, 4, 5, 6, 7] e elementToBeSearched = 4

4 está presente na matriz no índice 3.

Assim, 3 é retornado da função e "Elemento 4 encontrado no índice 3" é exibido na saída.

Exemplo 2 : Let arr = [1, 1, 1, 1, 1] e elementToBeSearched = 2

2 não está presente na matriz.

Portanto, -1 é retornado da função e "Elemento 2 não encontrado" é exibido na saída.

Abordagem para resolver o problema

  1. Compare o elemento a ser pesquisado com o elemento no índice mais à esquerda e o índice mais à direita na matriz.
  2. Se o elemento for encontrado, retorna o índice.
  3. Caso contrário, pesquise recursivamente o elemento para o resto da matriz, incrementando o índice esquerdo e diminuindo o índice direito.
  4. Chame a função recursivamente até que o índice direito seja menor que o índice esquerdo.

Relacionado: Como Encontrar a Soma de Todos os Elementos em uma Matriz

Programa C ++ para implementar o algoritmo de pesquisa linear usando recursão

Abaixo está o programa C ++ para implementar o algoritmo de pesquisa linear usando recursão:

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

Saída:

 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: Uma Introdução ao Algoritmo de Classificação de Mesclagem

Programa Python para implementar o algoritmo de pesquisa linear usando recursão

Abaixo está o programa Python para implementar o algoritmo de pesquisa linear usando recursão:

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

Saída:

 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: Como Encontrar a Soma dos Números Naturais Usando Recursão

Programa JavaScript para implementar o algoritmo de pesquisa linear usando recursão

Abaixo está o programa JavaScript para implementar o algoritmo de pesquisa linear usando recursão:

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

Saída:

 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: Uma Introdução ao Algoritmo de Classificação de Bolhas

Programa C para implementar o algoritmo de pesquisa linear usando recursão

Abaixo está o programa C para implementar o algoritmo de pesquisa linear usando recursão:

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

Saída:

 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

Aprenda a recursão

A recursão é um tópico de programação muito importante e divertido. A recursão é feita para resolver problemas que podem ser divididos em problemas menores e repetitivos. Pode ser um pouco difícil de aprender para programadores iniciantes, mas vale a pena aprender como resolver problemas usando recursão.