Dada una array arr[] de n elementos, escriba una función para buscar recursivamente un elemento dado x en arr[].
Ilustración:
Input : arr[] = {25, 60, 18, 3, 10}
Output : Element to be searched : 3
Input : arr[] = {10,20,30,24,15,40}
Output : -1
For x = 35
Element x is not present in arr[]
Procedimiento:
La idea es buscar el elemento desde ambos lados de la array de forma recursiva. Si el elemento que necesita buscar coincide con el elemento más a la izquierda del límite izquierdo, o coincide con el elemento más a la derecha del límite derecho, devuelva directamente la posición del elemento; de lo contrario, recurra a la array restante para buscar el elemento con el valor igual a x.
Ejemplo
Java
// Java Program to Search an element in an Array Recursively
// Main class
public class GFG {
// Method 1
// Recursive method to search for an element and
// its index in the array
static int recursiveSearch(int arr[], int l, int r,
int x)
{
// if r<l,it means that element is not present in
// the array
if (r < l)
return -1;
if (arr[l] == x)
return l;
if (arr[r] == x)
return r;
// Since element has not found on both left most and
// rightmost boundary,ie at l and r, now recursive the
// array to find position of x.
return recursiveSearch(arr, l + 1, r - 1, x);
}
// Method 2
// Main driver method
public static void main(String[] args)
{
// Element to be searched for
// Custom input number
int x = 3;
// Declaring and initializing the integer array
int arr[] = new int[] { 25, 60, 18, 3, 10 };
// Calling the above recursive method method to
// search for the element in the array
// Recursive function is called over array to
// get the index of the element present in an array
int index
= recursiveSearch(arr, 0, arr.length - 1, x);
// If index is found means element exists
if (index != -1)
// Print the element and its index
System.out.println("Element " + x
+ " is present at index "
+ index);
// If we hit else case means
// element is not present in the array
else
// Simply display the corresponding element
// is not present
System.out.println("Element " + x
+ " is not present");
}
}
Element 3 is present at index 3
Complejidad de tiempo : O(N 2 ) donde N es el tamaño de la array de entrada
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por lavishgarg26 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA