Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

java
binary
search
userdefined
communitycreator

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

abhilash

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.

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

public class Main {

    static 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 +
                    '}';
        }
    }

    static class StudentComparator implements Comparator<Student>{

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

    private static void print(Student student, int index){
        if(index < 0){
            System.out.println(student + " is not present in the list of students");
        }else {
            System.out.println(student + " is present in the list of students at index - " + index);
        }
    }

    public static void main(String[] args) {
        List<Student> studentList = new ArrayList<>();
        studentList.add(new Student("john",1001));
        studentList.add(new Student("keith",1003));
        studentList.add(new Student("donald", 1005));
        studentList.add(new Student("mac",1009));

        Student searchStudent = new Student("donald",1005);
        int index = Collections.binarySearch(studentList, searchStudent, new StudentComparator());
        print(searchStudent, index);

        Student searchStudent1 = new Student("mac",1005);
        int index1 = Collections.binarySearch(studentList, searchStudent1, new StudentComparator());
        print(searchStudent1, index1);
    }
}

RELATED TAGS

java
binary
search
userdefined
communitycreator
RELATED COURSES

View all Courses

Keep Exploring