Bifalgorithm post · Computer science one · Sorted Collections

How does Java perform binary searches on arrays and lists?

How does Java perform binary searches on arrays and lists? (Computer science one · Sorted Collections) — "The Arrays class provides public static int binarySea…

Ideas in this flowchart

Búsqueda binaria en arrays y colecciones de Java
Arrays.binarySearch con Comparator
Recibe un array, una clave y un Comparator del mismo tipo T
Devuelve el índice de un elemento coincidente
No garantiza devolver el primer elemento de la lista ordenada
Si no encuentra coincidencias, devuelve un valor negativo relacionado con el punto de inserción
Existe una versión que utiliza el orden natural de los elementos
En esta versión, los elementos deben implementar Comparable
Collections.binarySearch con Comparator
Recibe una List en lugar de un array y mantiene el mismo comportamiento
Los ejemplos muestran búsquedas mediante equals y mediante comparadores
La búsqueda mediante equals usa una clave con todos los campos coincidentes
La búsqueda por nombre ordena la lista con byName y usa una clave con nombre
La búsqueda por identificador ordena la lista con byId y usa una clave con identificador

Bifalgorithm

Feed/

How does Java perform binary searches on arrays and lists?

No cover

Channel

Computer science one

1 page

sam23

Ebook2w

"The Arrays class provides public static <T> int binarySearch(T[] a, T key, Comparator<T> c). That is, it takes an array of elements as well as key and a Comparator all of the same type T. It returns an integer representing the index at which it finds the first matching element (there is no guarantee that the first element in the sorted list is returned). If no match is found, then the method returns something negative. It actually returns a negative value corresponding to the insertion point at which the element would be if it had existed. Another version has the same behavior but can be called without a Comparator, relying instead on the natural ordering of elements. For this variation, the type of elements must implement the Comparable interface. The Collections class provides a similar method, public static <T> int binarySearch(List<T> list, T key, Comparator<T> c). The only difference is that the method takes a List instead of an array. Otherwise, the behavior is the same. We present several examples in Code Sample 36.1.\n\nArrayList<Student> roster = ...\n\nStudent castroKey = null;\n\nint castroIndex;\n\n//create a \"key\" that will match according to the\n\n// Student.equals() method\n\ncastroKey = new Student(\"Starlin\", \"Castro\", 131313, 3.95);\n\ncastroIndex = roster.indexOf(castroKey);\n\nSystem.out.println(\"at index \" + castroIndex + \": \" +\n\nroster.get(castroIndex));\n\n//create a key with only the necessary fields to match\n\n// the comparator\n\ncastroKey = new Student(\"Starlin\", \"Castro\", 0, 0.0);\n\n//sort the list according to the comparator\n\nCollections.sort(roster, byName);\n\ncastroIndex = Collections.binarySearch(roster, castroKey, byName);\n\nSystem.out.println(\"at index \" + castroIndex + \": \" +\n\nroster.get(castroIndex));\n\n//create a key with only the necessary fields to match\n\n// the comparator\n\ncastroKey = new Student(null, null, 131313, 0.0);\n\n//sort the list according to the comparator\n\nCollections.sort(roster, byId);\n\ncastroIndex = Collections.binarySearch(roster, castroKey, byId);\n\nSystem.out.println(\"at index \" + castroIndex + \": \" +\n\nroster.get(castroIndex));\n\nCode Sample 36.1.: Java Search Examples"

Flowchart preview

👍

0 comments0 shares