La interfaz Comparator en Java se puede utilizar para comparar objetos definidos por el usuario. La interfaz Comparator está presente en el paquete java.util . La búsqueda binaria es un algoritmo de búsqueda que utiliza la regla divide y vencerás para buscar la presencia de un elemento en una lista o array. El algoritmo de búsqueda binaria solo funciona en una lista ordenada. En caso de que la lista no esté ordenada, la búsqueda puede arrojar resultados indefinidos. Las clases predefinidas que implementan las interfaces de la colección también implementan la interfaz comparable. Por lo tanto, cuando se realiza una búsqueda binaria en los objetos de las clases contenedoras predefinidas, los objetos se ordenan en un orden natural y luego se realiza la búsqueda binaria en la lista ordenada. Por defecto, las clases definidas por el usuario no implementan elInterfaz comparable en Java. Para las clases definidas por el usuario, la interfaz Comparator es de gran utilidad. La interfaz Comparator permite la comparación de atributos específicos de la clase definida por el usuario. La interfaz Comparator también se puede utilizar para comparar dos objetos diferentes que pertenecen a diferentes clases. Las clases que implementan la interfaz Comparator anulan el método compare() de la interfaz. Los siguientes ejemplos tratan sobre la creación de objetos definidos por el usuario y el uso de la interfaz Comparator para clasificar los objetos y, finalmente, realizar una búsqueda binaria para obtener el índice del objeto requerido.
Sintaxis
public static int binarySearch(List list, T key)
Parámetros:
- list: Lista de objetos sobre los que se va a realizar la búsqueda binaria.
- clave: El objeto a encontrar
Valor devuelto: Devuelve el índice del elemento clave. Si no se encuentra el elemento clave, el índice devuelto es (-(punto de inserción) – 1).
Ejemplo 1:
Se crea una clase de estudiante con los atributos ID de estudiante, nombre de estudiante y calificaciones de estudiante. La lista de objetos de la clase Student no está ordenada. La lista de objetos de estudiantes se ordena usando el objeto comparador pasado al método Collections.sort() . La búsqueda binaria se realiza en la lista de estudiantes ordenada utilizando el método Collections,binarySearch() . Si se encuentra el objeto de destino, se devuelve el índice respectivo; de lo contrario, el índice devuelto es -(punto de inserción) – 1. El punto de inserción es el índice en el que se debe colocar el elemento de destino en la lista si no está presente. La identificación del estudiante es única para cada estudiante, por lo tanto, se usa para ordenar la lista de estudiantes. El método compare() se anula en StudentCompclase. El método compare() devuelve 0 si dos estudiantes tienen la misma identificación de estudiante, devuelve +1 si la identificación de estudiante de s1 es mayor que s2 y devuelve -1 en caso contrario. La lista de Estudiantes se ordena en orden ascendente. Finalmente, se llama a la búsqueda binaria en el objeto ordenado y el índice requerido se imprime en la consola.
Implementación de código
Java
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
class Student {
// attributes
int sid;
String name;
int marks;
// constructor
public Student(int sid, String name, int marks)
{
super();
this.sid = sid;
this.name = name;
this.marks = marks;
}
// returns student id
public int getSid() { return sid; }
// returns student name
public String getName() { return name; }
// returns marks
public int getMarks() { return marks; }
public void setSid(int sid) { this.sid = sid; }
public void setName(String name) { this.name = name; }
public void setMarks(int marks) { this.marks = marks; }
}
// Comparator to sort a list
class StudentComp implements Comparator<Student> {
@Override public int compare(Student s1, Student s2)
{
if (s1.getSid() == s2.getSid()) {
return 0;
}
else if (s1.getSid() > s2.getSid()) {
return 1;
}
else if (s1.getSid() < s2.getSid()) {
return -1;
}
return -1;
}
}
public class BinarySearchDemo {
public static void main(String[] args)
{
// list of students
ArrayList<Student> l = new ArrayList<Student>();
// Add students
l.add(new Student(100, "Jack", 95));
l.add(new Student(101, "Jane", 98));
l.add(new Student(199, "Mary", 90));
l.add(new Student(105, "Beck", 75));
l.add(new Student(104, "Betty", 85));
l.add(new Student(103, "Archie", 96));
l.add(new Student(108, "Nate", 89));
l.add(new Student(109, "Liam", 100));
// sort the list
Collections.sort(l, new StudentComp());
Student searchKey = new Student(109, "Liam", 100);
// index of the target
int index1 = Collections.binarySearch(
l, searchKey, new StudentComp());
System.out.println("Index of the searched key: "
+ index1);
searchKey = new Student(99, "Jennifer", 60);
int index2 = Collections.binarySearch(
l, searchKey, new StudentComp());
System.out.println("Index of the searched key: "
+ index2);
}
}
Index of the searched key: 6 Index of the searched key: -1
Ejemplo 2:
En este ejemplo, la lista de Estudiantes se ordena en orden descendente del atributo de calificaciones de la clase de Estudiante. Por lo tanto, los mismos objetos del ejemplo anterior ahora tienen un índice diferente. La búsqueda binaria se realiza en la nueva lista y, por lo tanto, el índice del elemento requerido se devuelve y se imprime en la salida.
Implementación de código
Java
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
class Student {
// attributes
int sid;
String name;
int marks;
// constructor
public Student(int sid, String name, int marks)
{
super();
this.sid = sid;
this.name = name;
this.marks = marks;
}
// returns student id
public int getSid() { return sid; }
// returns name
public String getName() { return name; }
// returns marks
public int getMarks() { return marks; }
public void setSid(int sid) { this.sid = sid; }
public void setName(String name) { this.name = name; }
public void setMarks(int marks) { this.marks = marks; }
}
// comparator to sort
class StudentComp implements Comparator<Student> {
@Override public int compare(Student s1, Student s2)
{
if (s1.getMarks() == s2.getMarks()) {
return 0;
}
else if (s1.getMarks() < s2.getMarks()) {
return 1;
}
return -1;
}
}
public class BinarySearchDemo {
public static void main(String[] args)
{
// list of students
ArrayList<Student> l = new ArrayList<Student>();
// Add students
l.add(new Student(100, "Jack", 95));
l.add(new Student(101, "Jane", 98));
l.add(new Student(199, "Mary", 90));
l.add(new Student(105, "Beck", 75));
l.add(new Student(104, "Betty", 85));
l.add(new Student(103, "Archie", 96));
l.add(new Student(108, "Nate", 89));
l.add(new Student(109, "Liam", 100));
// sort the list
Collections.sort(l, new StudentComp());
for (int i = 0; i < l.size(); i++)
System.out.println(i + " " + l.get(i).getName()
+ " " + l.get(i).getMarks());
// search the target
Student searchKey = new Student(109, "Liam", 100);
int index1 = Collections.binarySearch(
l, searchKey, new StudentComp());
System.out.println("Index of the searched key: "
+ index1);
searchKey = new Student(99, "Jennifer", 60);
int index2 = Collections.binarySearch(
l, searchKey, new StudentComp());
System.out.println("Index of the searched key: "
+ index2);
}
}
0 Liam 100 1 Jane 98 2 Archie 96 3 Jack 95 4 Mary 90 5 Nate 89 6 Betty 85 7 Beck 75 Index of the searched key: 0 Index of the searched key: -9
Publicación traducida automáticamente
Artículo escrito por Shreyasi_Chakraborty y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA