Programa Java para realizar búsquedas binarias en ArrayList

La clase ArrayList es parte del marco de la colección y está presente en el paquete java.util. Nos proporciona arrays dinámicas o de tamaño variable en Java. Es bastante más lento que las arrays estándar, pero puede ser útil en algunos programas en los que necesitamos crear un código más limpio y más corto y se necesita mucha manipulación de una array.

El algoritmo más eficaz para buscar un elemento en una array ordenada es el algoritmo de búsqueda binaria . En este artículo, vamos a implementar esto usando Java ArrayList.

Enfoques:

Hay tres formas de implementar la búsqueda binaria en Java ArrayList que se enumeran a continuación para resumir el concepto seguido de un ejemplo de Java para la parte de implementación.

1. Búsqueda binaria iterativa (búsqueda binaria normal mediante bucle)
2. Búsqueda binaria recursiva (búsqueda binaria mediante recursividad )
3. Usando el método de búsqueda binaria incorporado de las colecciones de Java.

Método 1: búsqueda binaria iterativa

En este enfoque, ignoramos la mitad de los elementos después de una comparación. A medida que se ordena la array.

• Compare el valor dado a buscar con el elemento del medio.
• Si coincide con el elemento del medio, devolvemos x.
• Si es mayor que el elemento del medio, haga lo mismo para el subarreglo derecho, es decir. el tamaño del arreglo se reduce a la mitad y el arreglo que nos queda para comparar es el subarreglo derecho.
• Si es menor que el elemento del medio, haga lo mismo para el subarreglo izquierdo, es decir. el tamaño del arreglo se reduce a la mitad y el arreglo que nos queda para comparar es el subarreglo izquierdo.
• Si no devolvemos nada pero nuestra búsqueda finaliza, entonces devolvemos -1, implica que el elemento no está presente en esa array.

// Java program to print binary search over an ArrayList
  
import java.io.*;
import java.util.*;
  
class BinarySearch 
{ 
    // Returns index of x if it is present in arr[], 
    // else return -1 
    int binarySearch(ArrayList<Integer> arr, int x) 
    { 
        int left = 0, right = arr.size() - 1; 
        
        while (left <= right)
        { 
            int mid = left + (right - left) / 2; 
    
            // Check if x is present at mid 
            if (arr.get(mid) == x) 
                return mid; 
    
            // If x greater, ignore left half 
            if (arr.get(mid) < x) 
                left = mid + 1; 
    
            // If x is smaller, ignore right half 
            else
                right = mid - 1; 
        } 
    
        // if we reach here, then element was 
        // not present 
        return -1; 
    } 
    
    // Driver method to test above 
    public static void main(String args[]) 
    { 
        BinarySearch ob = new BinarySearch(); 
        
        ArrayList<Integer> arr = new ArrayList<Integer>();
        
        arr.add(5);
        arr.add(10);
        arr.add(15);
        arr.add(20);
        arr.add(25);
        arr.add(30);
        arr.add(35); 
        
        int x = 10; 
        
        // Printing elements of array list
        System.out.println("The elements of the arraylist are: "+arr);
        
        int result = ob.binarySearch(arr, x); 
        
        if (result == -1) 
            System.out.println("Element not present"); 
        
        else
            System.out.println("The Element " + x + " is found at "
                               + "index " + result); 
    } 
} 

The elements of the arraylist are: [5, 10, 15, 20, 25, 30, 35]
The Element 10 is found at index 1

Método 2: búsqueda binaria recursiva

• Compare el elemento que se busca (x) con el elemento del medio.
• Si x coincide con el elemento medio, devolvemos el índice medio.
• 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 a la mitad derecha.
• De lo contrario (x es menor) se repite para la mitad izquierda.

// Java implementation of recursive Binary Search
  
import java.io.*;
import java.util.*;
  
class BinarySearch
{ 
    // Returns index of x if it is present in arr[l.. 
    // r], else return -1 
    
    int binarySearch(ArrayList<Integer> 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.get(mid) == x) 
                return mid; 
  
            // If element is smaller than mid, then 
            // it can only be present in left subarray 
            if (arr.get(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); 
        } 
  
        // We reach here when element is not present 
        // in array 
        return -1; 
    } 
  
    // Driver method to test above 
    public static void main(String args[]) 
    { 
        BinarySearch ob = new BinarySearch(); 
        
        ArrayList<Integer> arr = new ArrayList<Integer>();
        arr.add(5);
        arr.add(10);
        arr.add(15);
        arr.add(20);
        arr.add(25);
        arr.add(30);
        arr.add(35); 
        
        int n = arr.size();
        
        // We will find x inside the arraylist
        int x = 10; 
        
        // Printing elements of array list
        System.out.println("The elements of the arraylist are: "+arr);
        
        int result = ob.binarySearch(arr,0,n-1,x); 
        
        if (result == -1) 
            System.out.println("Element not present"); 
        else
            System.out.println("The Element " + x + " is found at "
                               + "index " + result); 
    } 
}

The elements of the arraylist are: [5, 10, 15, 20, 25, 30, 35]
The Element 10 is found at index 1

Método 3: usar el método binarySearch integrado de la clase Collections

En este método, simplemente llamamos al método binarySearch() del marco de colecciones y analizamos nuestra ArrayList ordenada y el valor que se buscará en el método. Esto devolverá el índice del elemento si está presente y -1 de lo contrario.

// Java program to demonstrate the searching of
// an element in ArrayList using binarySearch() 
// of Collections class
  
import java.util.ArrayList;
import java.util.Collections;
  
public class BinarySearch {
    
    public static void main(String[] args)
    {
        ArrayList<Integer> arr = new ArrayList<Integer>();
        
        arr.add(5);
        arr.add(10);
        arr.add(15);
        arr.add(20);
        arr.add(25);
        arr.add(30);
        arr.add(35); 
        
        // Initializing the key to be found.
        int val = 10; 
        
        // Printing elements of array list
        System.out.println("The elements of the arraylist are: "+arr);
        
        // Implementing the built-in binarySearch method from collections
        int result = Collections.binarySearch(arr,val);
        
        if (result == -1) 
            System.out.println("Element not present"); 
        else
            System.out.println("The Element " + val + " is found at "
                               + "index " + result); 
    } 
}

The elements of the arraylist are: [5, 10, 15, 20, 25, 30, 35]
The Element 10 is found at index 1