Búsqueda binaria de colecciones en Java

1. Algoritmo Básico de Búsqueda Binaria
2. Sintaxis de Collections.binarySearch() en Java
3. Tipos de búsquedas utilizando Collections.binarySearch() en Java
4. Conclusión

La clase Collections de Java tiene un método interno llamado binarySearch() que devuelve la posición del objeto en una lista ordenada. El parámetro de la función Collections binarySearch() permite diferenciar en función de los distintos parámetros del script.

El algoritmo de búsqueda binaria es utilizado por Collections.binarySearch() para buscar en la lista proporcionada el objeto solicitado. Antes de realizar esta llamada, la lista debe ordenarse en orden ascendente utilizando el orden natural de sus elementos.

Si no se ordena, los resultados no son claros. No hay certeza de que se localizará el elemento deseado si la lista contiene muchos elementos idénticos al objeto solicitado.

Algoritmo Básico de Búsqueda Binaria

En la búsqueda binaria, la colección se divide repetidamente por la mitad. Dependiendo de si el elemento clave es menor o mayor que el elemento central de la colección, se busca el elemento clave en la mitad izquierda o derecha de la colección.

Pasos a seguir en un algoritmo de búsqueda binaria:

1. Determine el punto medio de la colección.
2. Compare el elemento medio con los componentes esenciales.
3. Devuelve la posición de índice medio para la clave descubierta si la clave es la misma que el elemento central.
4. De lo contrario, si la clave > elemento medio, la clave está en la mitad derecha de la colección. Repita los pasos 1 a 3 para completar la mitad inferior (derecha) de la colección.
5. Si la clave es un elemento intermedio, entonces la clave está en la mitad superior de la colección. Como resultado, debe realizar la búsqueda binaria nuevamente en la mitad superior.

Sintaxis de Collections.binarySearch() en Java

La siguiente sintaxis se utiliza para declarar este método.

public static <T> int binarySearch(List<? extends Comparable<? super T>> list,
    T key) public static <T> int binarySearch(List<? extends T> list, T key,
    Comparator<? super T> c)

Hay 2 tipos de métodos Collections.binarySearch():

1. Colecciones Java binarySearch(List<? extends Comparable<? super T>> list, T key).

   Antes de utilizar el procedimiento, la lista debe ordenarse en orden ascendente utilizando el número natural proporcionado. Los resultados son indefinibles si la lista no está ordenada.

2. Colecciones Java binarySearch(List<? extends T> list, T key, Comparator<? super T> c).

   Antes de llamar al procedimiento, la lista debe ordenarse de forma ascendente utilizando el comparador suministrado.

Tipos de búsquedas utilizando Collections.binarySearch() en Java

Para que binarySearch() funcione según lo previsto, el comparador proporcionado debe ordenar sus datos. Antes de realizar esta llamada, la lista debe ordenarse en orden ascendente utilizando el comparador suministrado.

El procedimiento proporcionará el índice del elemento buscado si los datos están ordenados; de lo contrario, devolverá (-(punto de inserción) - 1).

Buscar una clave entera en una lista ordenada ascendente.

Código de ejemplo:

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Main {
  public static void main(String[] args) {
    List<Integer> al = new ArrayList<Integer>();
    al.add(3);
    al.add(4);
    al.add(5);
    al.add(20);
    al.add(30);

    int index = Collections.binarySearch(al, 20);
    System.out.println(index);

    index = Collections.binarySearch(al, 12);
    System.out.println(index);
  }
}

Producción :

3
-4

Busque una clave entera en una lista ordenada descendente.

Código de ejemplo:

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Main {
  public static void main(String[] args) {
    List<Integer> al = new ArrayList<Integer>();
    al.add(350);
    al.add(90);
    al.add(45);
    al.add(20);
    al.add(3);

    int index = Collections.binarySearch(al, 45, Collections.reverseOrder());

    System.out.println(index);
  }
}

Producción :

2

Conclusión

Las Colecciones binarySearch() es el método de búsqueda más popular. Aquí, la condición es que los datos deben clasificarse en orden ascendente para que una búsqueda binaria tenga éxito.

Se pueden usar métodos iterativos o recursivos para implementar una búsqueda binaria. La clase Java Arrays ofrece además el método binarySearch(), que realiza una búsqueda binaria en una matriz.