Binary search on a list of user-defined objects in Java

This shot discusses how to use binary search to search on a list of user-defined objects in Java.

What is binary search?

Binary search is an efficient method to locate an element in a sorted array.

Consider the following Student class. It has two different attributes: studentId and name.

class Student{
        public String name;
        public int studentId;

        public Student(String name, int studentId) {
            this.name = name;
            this.studentId = studentId;
        }

        @Override
        public String toString() {
            return "Student{" +
                    "name='" + name + '\'' +
                    ", studentId=" + studentId +
                    '}';
        }
    }

Given a list of student objects, search for a specific student object through binary search.

Collections.binarySearch

Collections.binarySearch uses the binary search algorithm to search for a specified object in a sorted list.

The method signature is as follows.

public static <T> int binarySearch(List<? extends T> list, T key, Comparator<? super T> c)

The method accepts a list to be searched, a key to be searched for, and a comparator by which the list is ordered.

If the key is found in the list, then the method returns a positive value that indicates the index where the key is located.

If the key is not found in the list, then the method returns a negative value.

Comparator interface

The Comparator provides a custom sorting order for a data structure.

Let’s define a comparator for the Student class.

class StudentComparatorById implements Comparator<Student>{

        @Override
        public int compare(Student o1, Student o2) {
            return (o1.studentId == o2.studentId) && (o1.name.equals(o2.name))?0:-1;
        }
    }

The comparator above checks the equality condition of the student attributes for the student objects.

Complete code

The example below will help you understand the binary search on custom objects better. We first define a list and populate the list with student objects. We then define a student object which has to be searched in the list. Then, we search for the student object in the list through the binarySearch function by passing a student comparator object.