The Comparator interface in Java can be used to compare user-defined objects. The Comparator interface is present in java.util package. Binary search is a searching algorithm that uses the divide and conquers rule to search the presence of an element in a list or array. The binary search algorithm works only on a sorted list. In case the list is not sorted the search may return undefined results. The predefined classes that implement the Collection interfaces also implement the comparable interface. Hence, when a binary search is performed on the objects of the predefined wrapper classes the objects are sorted in a natural order and then the binary search is performed on the sorted list. By default, user-defined classes do not implement the Comparable interface in Java. For user-defined classes, the Comparator interface is of great use. The Comparator interface allows the comparison of specific attributes of the user-defined class. The Comparator interface can also be used to compare two different objects belonging to different classes. Classes that implement the Comparator interface override the compare() method of the interface. The following examples deal with creating user-defined objects and using the Comparator interface to sort the objects and finally perform a binary search to get the index of the required object.
Syntax
public static int binarySearch(List list, T key)
Parameters:
- list: Object list on which binary search is to be performed.
- key: The object to be found
Return Value: Returns the index of the key element. If the key element is not found the index returned is (-(insertion point) – 1).
Example 1:
A student class is created with attributes student id, student name, and student marks. The Student class object list is not in sorted order. The student object list is sorted using the comparator object passed to Collections.sort() method. The binary search is performed on the sorted Student list using Collections,binarySearch() method. If the target object is found the respective index is returned else the index returned is -(insertion point) – 1. The insertion point is the index where the target element must be placed on the list if it is not present. The student id is unique for every student hence it is used to sort the Student list. The compare() method is overridden in the StudentComp class. The compare() method returns 0 if two students have the same student id, returns +1 if the student id of s1 is greater than s2, and returns -1 otherwise. The Student list is sorted in ascending order. Finally, binary search is called on the sorted and the index required object is printed to the console.
Code Implementation
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 listclass 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
Example 2:
In this example, the Student list is sorted in descending order of the marks attribute of the Student class. Therefore, the same objects of the previous example now have a different index. The binary search is performed on the new list and thus the index of the required element is returned and printed to the output.
Code Implementation
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 sortclass 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
