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
// 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