Búsqueda binaria en Java

Introducción

La búsqueda binaria es un algoritmo de búsqueda eficiente utilizado para encontrar un valor en una matriz ordenada. Es más rápido que la búsqueda lineal porque elimina la mitad de la matriz después de cada iteración. En este laboratorio, aprenderemos los pasos para implementar el algoritmo de búsqueda binaria en Java.

Skills Graph

Crear una matriz ordenada

El algoritmo de búsqueda binaria requiere una matriz ordenada, por lo que primero crearemos una matriz ordenada.

int[] sortedArray = {2, 4, 6, 8, 10, 12, 14, 16, 18, 20};

Implementar la búsqueda binaria de forma iterativa

Ahora implementaremos el algoritmo de búsqueda binaria de forma iterativa. Este método devuelve el índice del elemento si está presente en la matriz. De lo contrario, devuelve -1.

public static int binarySearchIterative(int[] sortedArray, int key) {
    int leftIdx = 0;
    int rightIdx = sortedArray.length - 1;
    while (leftIdx <= rightIdx) {
        int midIdx = leftIdx + (rightIdx - leftIdx) / 2;
        if (sortedArray[midIdx] == key)
            return midIdx;
        else if (sortedArray[midIdx] > key) {
            rightIdx = midIdx - 1;
        } else
            leftIdx = midIdx + 1;
    }
    return -1;
}

Para ejecutar el código, primero debemos llamar al método binarySearchIterative, pasando sortedArray y el elemento que queremos buscar como parámetros.

## compilar el archivo java
javac BinarySearch.java

## ejecutar el archivo
java BinarySearch

Implementar la búsqueda binaria de forma recursiva

Ahora implementaremos el algoritmo de búsqueda binaria de forma recursiva. Este método también devuelve el índice del elemento si está presente en la matriz. De lo contrario, devuelve -1.

public static int binarySearchRecursive(int[] sortedArray, int key, int leftIdx, int rightIdx) {
    if (leftIdx <= rightIdx) {
        int midIdx = leftIdx + (rightIdx - leftIdx) / 2;
        if (sortedArray[midIdx] == key)
            return midIdx;
        else if (sortedArray[midIdx] > key) {
            return binarySearchRecursive(sortedArray, key, leftIdx, midIdx - 1);
        } else
            return binarySearchRecursive(sortedArray, key, midIdx + 1, rightIdx);
    } else
        return -1;
}

Para ejecutar el código, debemos llamar al método binarySearchRecursive, pasando sortedArray, el elemento que queremos buscar, leftIdx y rightIdx como parámetros.

Utilizar métodos incorporados para la búsqueda binaria

También tenemos funciones incorporadas en Java para implementar la búsqueda binaria. Estas funciones son Arrays.binarySearch() y Collections.binarySearch(). Podemos utilizar estas funciones para buscar un elemento en una matriz ordenada.

La función Arrays.binarySearch() toma una matriz ordenada y un valor de clave para buscar como parámetros. La función devuelve el índice de la clave si está presente en la matriz. De lo contrario, devuelve -1.

int index = Arrays.binarySearch(sortedArray, 6);

La función Collections.binarySearch() se puede utilizar en colecciones como ArrayLists para buscar un elemento. La función toma la colección ordenada y una clave como parámetros y devuelve el índice en el que se encuentra la clave. De lo contrario, devuelve -1.

ArrayList<Integer> sortedList = new ArrayList<Integer>(Arrays.asList(2, 4, 6, 8, 10, 12, 14, 16, 18, 20));
int index = Collections.binarySearch(sortedList, 6);

Prueba

Ahora probaremos todos los métodos y mostraremos la salida.

public static void main(String[] args) {
    int[] sortedArray = {2, 4, 6, 8, 10, 12, 14, 16, 18, 20};
    int key = 12;
    System.out.println("Element " + key + " is present at index: " + binarySearchIterative(sortedArray, key));
    System.out.println("Element " + key + " is present at index: " + binarySearchRecursive(sortedArray, key, 0, sortedArray.length - 1));
    System.out.println("Element " + key + " is present at index: " + Arrays.binarySearch(sortedArray, key));
    ArrayList<Integer> sortedList = new ArrayList<Integer>(Arrays.asList(2, 4, 6, 8, 10, 12, 14, 16, 18, 20));
    System.out.println("Element " + key + " is present at index: " + Collections.binarySearch(sortedList, key));
}

Para ejecutar el código, primero compilamos el programa Java.

javac BinarySearch.java

Luego podemos ejecutar el programa.

java BinarySearch

Resumen

Esta práctica cubrió los pasos necesarios para implementar el algoritmo de búsqueda binaria de forma iterativa y recursiva en el lenguaje de programación Java. También aprendimos sobre los métodos incorporados Arrays.binarySearch() y Collections.binarySearch() para implementar la búsqueda binaria. Creamos una matriz ordenada y utilizamos diferentes métodos para buscar elementos en ella.