Java Collections binarySearch() Method

The binarySearch() method in Java provides an efficient way to search for a specified element in a sorted list. It uses the binary search algorithm, which significantly reduces the search time by repeatedly dividing the list in half until the desired element is found.

Table of Contents

1. Introduction
2. binarySearch() Method Syntax
3. Examples
   • Basic Usage with Comparable
   • Usage with Comparator
4. Real-World Use Case
5. Conclusion

Introduction

The Collections.binarySearch() method is part of the java.util.Collections class and is designed to perform binary search on sorted lists. The method comes in two variations:

1. Using Natural Ordering: Searches a list of elements that implement the Comparable interface.
2. Using a Comparator: Searches a list using a specified Comparator to define the order.

Binary search is an efficient algorithm with a time complexity of O(log n), making it ideal for quickly locating elements in large datasets. However, the list must be sorted in ascending order before calling binarySearch().

binarySearch() Method Syntax

There are two overloaded versions of the binarySearch() method:

1. Using Natural Ordering

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

Parameters:

• list: The list to be searched, which must implement Comparable.
• key: The element to be searched for.

Returns:

• The index of the key, if it is present in the list; otherwise, (-(insertion point) - 1).

Throws:

• ClassCastException if the list contains elements that are not mutually comparable.

2. Using a Comparator

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

Parameters:

• list: The list to be searched.
• key: The element to be searched for.
• c: The comparator used to order the list.

Returns:

• The index of the key, if it is present in the list; otherwise, (-(insertion point) - 1).

Throws:

• ClassCastException if the list and the comparator are incompatible.

Examples

Basic Usage with Comparable

The following example demonstrates how to use the binarySearch() method with a list of elements that implement the Comparable interface, using a Student class with Indian names.

Example

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

class Student implements Comparable<Student> {
    String name;
    int rollNumber;

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

    @Override
    public int compareTo(Student other) {
        return Integer.compare(this.rollNumber, other.rollNumber);
    }

    @Override
    public String toString() {
        return name + " (Roll Number: " + rollNumber + ")";
    }
}

public class BinarySearchExample {
    public static void main(String[] args) {
        List<Student> students = new ArrayList<>();
        students.add(new Student("Aarav", 101));
        students.add(new Student("Vikram", 102));
        students.add(new Student("Priya", 103));
        students.add(new Student("Ananya", 104));

        // Sort the list based on roll numbers
        Collections.sort(students);

        // Search for a student with roll number 103
        int index = Collections.binarySearch(students, new Student("", 103));
        if (index >= 0) {
            System.out.println("Found: " + students.get(index));
        } else {
            System.out.println("Student not found.");
        }

        // Search for a student with roll number 105 (not found)
        index = Collections.binarySearch(students, new Student("", 105));
        if (index >= 0) {
            System.out.println("Found: " + students.get(index));
        } else {
            System.out.println("Student not found. Index: " + index);
        }
    }
}

Output:

Found: Priya (Roll Number: 103)
Student not found. Index: -5

Usage with Comparator

This example shows how to use the binarySearch() method with a custom comparator to search for students based on names.

Example

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

class Student {
    String name;
    int rollNumber;

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

    @Override
    public String toString() {
        return name + " (Roll Number: " + rollNumber + ")";
    }
}

public class BinarySearchWithComparator {
    public static void main(String[] args) {
        List<Student> students = new ArrayList<>();
        students.add(new Student("Aarav", 101));
        students.add(new Student("Vikram", 102));
        students.add(new Student("Priya", 103));
        students.add(new Student("Ananya", 104));

        // Sort by name
        students.sort(Comparator.comparing(student -> student.name));

        // Binary search for a student with name "Priya"
        int index = Collections.binarySearch(students, new Student("Priya", 0), Comparator.comparing(student -> student.name));
        if (index >= 0) {
            System.out.println("Found: " + students.get(index));
        } else {
            System.out.println("Student not found.");
        }

        // Binary search for a student with name "Rohan" (not found)
        index = Collections.binarySearch(students, new Student("Rohan", 0), Comparator.comparing(student -> student.name));
        if (index >= 0) {
            System.out.println("Found: " + students.get(index));
        } else {
            System.out.println("Student not found. Index: " + index);
        }
    }
}

Output:

Found: Priya (Roll Number: 103)
Student not found. Index: -4

Real-World Use Case

Searching in a Sorted List of Students

In educational software applications, the binarySearch() method can be used to quickly locate students in a sorted list by their roll numbers or names. This is especially useful for large datasets where efficiency is crucial.

Example

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

class Student {
    String name;
    int rollNumber;

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

    @Override
    public String toString() {
        return name + " (Roll Number: " + rollNumber + ")";
    }
}

public class StudentSearchExample {
    public static void main(String[] args) {
        List<Student> students = new ArrayList<>();
        students.add(new Student("Aarav", 101));
        students.add(new Student("Vikram", 102));
        students.add(new Student("Priya", 103));
        students.add(new Student("Ananya", 104));

        // Sort students by roll number
        Collections.sort(students, (s1, s2) -> Integer.compare(s1.rollNumber, s2.rollNumber));

        // Search for a student with roll number 104
        int index = Collections.binarySearch(students, new Student("", 104), (s1, s2) -> Integer.compare(s1.rollNumber, s2.rollNumber));
        if (index >= 0) {
            System.out.println("Found: " + students.get(index));
        } else {
            System.out.println("Student not found.");
        }
    }
}

Output:

Found: Ananya (Roll Number: 104)

Conclusion

The Collections.binarySearch() method is a powerful utility for efficiently locating elements in sorted lists. It supports both natural ordering and custom ordering using comparators, making it versatile for various search requirements. By understanding and using binarySearch(), you can significantly improve the performance of search operations in your Java applications, especially when working with large datasets.