Collections.binarySearch() en Java con ejemplos

El método java.util.Collections.binarySearch() es un método de clase java.util.Collections que devuelve la posición de un objeto en una lista ordenada.
 

// Returns index of key in sorted list sorted in
// ascending order
public static int binarySearch(List slist, T key)

// Returns index of key in sorted list sorted in
// order defined by Comparator c.
public static int binarySearch(List slist, T key, Comparator c)

If key is not present, the it returns "(-(insertion point) - 1)". 
The insertion point is defined as the point at which the key 
would be inserted into the list.

El método lanza ClassCastException si los elementos de la lista no son comparables usando el comparador especificado, o la clave de búsqueda no es comparable con los elementos.
Buscando una clave int en una lista ordenada en orden ascendente: 
 

Java

// Java program to demonstrate working of Collections.
// binarySearch()
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
  
public class GFG {
    public static void main(String[] args)
    {
        List<Integer> al = new ArrayList<Integer>();
        al.add(1);
        al.add(2);
        al.add(3);
        al.add(10);
        al.add(20);
  
        // 10 is present at index 3.
        int index = Collections.binarySearch(al, 10);
        System.out.println(index);
  
        // 13 is not present. 13 would have been inserted
        // at position 4. So the function returns (-4-1)
        // which is -5.
        index = Collections.binarySearch(al, 13);
        System.out.println(index);
    }
}

Producción : 

3
-5

Búsqueda de una clave int en una lista ordenada en orden descendente. 
 

java-collection-framework-fundamentals-self-paced

Java

// Java program to demonstrate working of Collections.
// binarySearch() in an array sorted in descending order.
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
  
public class GFG {
    public static void main(String[] args)
    {
        List<Integer> al = new ArrayList<Integer>();
        al.add(100);
        al.add(50);
        al.add(30);
        al.add(10);
        al.add(2);
  
        // The last parameter specifies the comparator
        // method used for sorting.
        int index = Collections.binarySearch(
            al, 50, Collections.reverseOrder());
  
        System.out.println("Found at index " + index);
    }
}

Producción : 

Found at index 1

Búsqueda en una lista de objetos de clase definidos por el usuario: 
 

Java

// Java program to demonstrate working of Collections.
// binarySearch() in a list of user defined objects
import java.util.*;
  
class Binarysearch {
    public static void main(String[] args)
    {
        // Create a list
        List<Domain> l = new ArrayList<Domain>();
        l.add(new Domain(10, "quiz.geeksforgeeks.org"));
        l.add(new Domain(20, "practice.geeksforgeeks.org"));
        l.add(new Domain(30, "code.geeksforgeeks.org"));
        l.add(new Domain(40, "www.geeksforgeeks.org"));
  
        Comparator<Domain> c = new Comparator<Domain>() {
            public int compare(Domain u1, Domain u2)
            {
                return u1.getId().compareTo(u2.getId());
            }
        };
  
        // Searching a domain with key value 10. To search
        // we create an object of domain with key 10.
        int index = Collections.binarySearch(
            l, new Domain(10, null), c);
        System.out.println("Found at index  " + index);
  
        // Searching an item with key 5
        index = Collections.binarySearch(
            l, new Domain(5, null), c);
        System.out.println(index);
    }
}
  
// A user-defined class to store domains with id and url
class Domain {
    private int id;
    private String url;
  
    // Constructor
    public Domain(int id, String url)
    {
        this.id = id;
        this.url = url;
    }
  
    public Integer getId() { return Integer.valueOf(id); }
}

Producción : 

0
-1

Arrays .binarysearch() vs Collections.binarySearch() 
Arrays.binarysearch() funciona para arrays que también pueden ser de tipo de datos primitivo. Colecciones .binarysearch() funciona para objetos Colecciones como ArrayList y LinkedList
Puntos importantes: 
 

  • Si la lista de entrada no está ordenada, los resultados no están definidos.
  • Si hay duplicados, no hay garantía de cuál se encontrará.
  • Este método se ejecuta en tiempo de registro (n) para una lista de «acceso aleatorio» como ArrayList. Si la lista especificada no implementa la interfaz RandomAccess y es grande, este método realizará una búsqueda binaria basada en iteradores que realiza cruces de enlaces O(n) y comparaciones de elementos O(log n).

Referencia: 
https://docs.oracle.com/javase/7/docs/api/java/util/Collections.html#binarySearch(java.util.List,%20T) Mohit Gupta
contribuye con este artículo . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo y enviarlo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks. Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.

 

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 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 *