Programa Java para buscar recursivamente linealmente un elemento en una array

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");
    }
}
Producción

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *