Algoritmos de búsqueda en Java

Los algoritmos de búsqueda están diseñados para verificar un elemento o recuperar un elemento de cualquier estructura de datos donde esté almacenado. Según el tipo de operación de búsqueda, estos algoritmos generalmente se clasifican en dos categorías:
 

1. Búsqueda secuencial: en esta, la lista o array se recorre secuencialmente y se verifica cada elemento. Por ejemplo: búsqueda lineal .
2. Búsqueda de intervalo: estos algoritmos están diseñados específicamente para buscar en estructuras de datos ordenadas. Este tipo de algoritmos de búsqueda son mucho más eficientes que la búsqueda lineal, ya que apuntan repetidamente al centro de la estructura de búsqueda y dividen el espacio de búsqueda por la mitad. Por ejemplo: búsqueda binaria .

Búsqueda lineal : la idea es recorrer la array dada arr[] y encontrar el índice en el que está presente el elemento. A continuación se muestran los pasos:
 

• Sea x el elemento a buscar .
• Comience desde el elemento más a la izquierda de arr[] y, uno por uno, compare x con cada elemento de arr[] .
• Si x coincide con un elemento, devuelve ese índice .
• Si x no coincide con ninguno de los elementos, devuelva -1.

A continuación se muestra la implementación de la búsqueda secuencial en Java:
 

// Java program to implement Linear Search
 
class GFG {
 
    // Function for linear search
    public static int search(int arr[], int x)
    {
        int n = arr.length;
 
        // Traverse array arr[]
        for (int i = 0; i < n; i++) {
 
            // If element found then
            // return that index
            if (arr[i] == x)
                return i;
        }
        return -1;
    }
 
    // Driver Code
    public static void main(String args[])
    {
        // Given arr[]
        int arr[] = { 2, 3, 4, 10, 40 };
 
        // Element to search
        int x = 10;
 
        // Function Call
        int result = search(arr, x);
        if (result == -1)
            System.out.print(
                "Element is not present in array");
        else
            System.out.print("Element is present"
                             + " at index "
                             + result);
    }
}

Element is present at index 3

Complejidad temporal: O(N) 
Espacio auxiliar: O(1) 

Búsqueda binaria : este elemento de búsqueda de algoritmo en una array ordenada divide repetidamente el intervalo de búsqueda por la mitad. Comience con un intervalo que cubra todo el arreglo. Si el valor de la clave de búsqueda es menor que el elemento en el medio del intervalo, reduzca el intervalo a la mitad inferior. De lo contrario, redúcelo a la mitad superior. Verifique repetidamente hasta que se encuentre el valor o el intervalo esté vacío. A continuación se muestran los pasos:
 

1. Compara x con el elemento del medio.
2. Si x coincide con el elemento medio, devolvemos el índice medio.
3. De lo contrario, si x es mayor que el elemento medio, entonces x solo puede estar en el medio subarreglo derecho después del elemento medio. Entonces recurrimos para la mitad derecha.
4. De lo contrario (x es menor) se repite para la mitad izquierda.

Implementación recursiva de búsqueda binaria

// Java implementation of recursive
// Binary Search
 
class BinarySearch {
 
    // Function that returns index of
    // x if it is present in arr[l, r]
    int binarySearch(int arr[], int l,
                     int r, int x)
    {
        if (r >= l) {
            int mid = l + (r - l) / 2;
 
            // If the element is present
            // at the middle itself
            if (arr[mid] == x)
                return mid;
 
            // If element is smaller than
            // mid, then it can only be
            // present in left subarray
            if (arr[mid] > x)
                return binarySearch(arr, l,
                                    mid - 1, x);
 
            // Else the element can only be
            // present in right subarray
            return binarySearch(arr, mid + 1,
                                r, x);
        }
 
        // Reach here when element is
        // not present in array
        return -1;
    }
 
    // Driver Code
    public static void main(String args[])
    {
 
        // Create object of this class
        BinarySearch ob = new BinarySearch();
 
        // Given array arr[]
        int arr[] = { 2, 3, 4, 10, 40 };
        int n = arr.length;
        int x = 10;
 
        // Function Call
        int result = ob.binarySearch(arr, 0,
                                     n - 1, x);
 
        if (result == -1)
            System.out.println("Element "
                               + "not present");
        else
            System.out.println("Element found"
                               + " at index "
                               + result);
    }
}

Element found at index 3

Complejidad de tiempo: O(N*log N) 
Espacio auxiliar: O(1) 

Implementación iterativa de búsqueda binaria

// Java implementation of iterative
// Binary Search
 
class BinarySearch {
 
    // Returns index of x if it is present
    // in arr[], else return -1
    int binarySearch(int arr[], int x)
    {
 
        int l = 0, r = arr.length - 1;
 
        // Iterate until l <= r
        while (l <= r) {
            int m = l + (r - l) / 2;
 
            // Check if x is at mid
            if (arr[m] == x)
                return m;
 
            // If x greater than arr[m]
            // then ignore left half
            if (arr[m] < x)
                l = m + 1;
 
            // If x is smaller than arr[m]
            // ignore right half
            else
                r = m - 1;
        }
 
        // If we reach here, then element
        // was not present
        return -1;
    }
 
    // Driver Code
    public static void main(String args[])
    {
 
        // Create object of this class
        BinarySearch ob = new BinarySearch();
 
        // Given array arr[]
        int arr[] = { 2, 3, 4, 10, 40 };
        int n = arr.length;
        int x = 10;
 
        // Function Call
        int result = ob.binarySearch(arr, x);
 
        if (result == -1)
            System.out.println("Element not present");
        else
            System.out.println("Element found at index "
                               + result);
    }
}

Element found at index 3

Complejidad temporal: O(N) 
Espacio auxiliar: O(1)