Binary search in ArrayList in Java

You can perform a binary search on an ArrayList, but there are a few rules and differences compared to arrays. Let me explain step by step.

1️⃣ Rules for Binary Search

1. ArrayList must be sorted before performing binary search.

2. Use Collections.binarySearch() method for ArrayLists.

3. The method returns:

Index of the element if found

-(insertion point) - 1 if not found

2️⃣ Example: Binary Search on ArrayList

import java.util.*;

class Employee {
    int id;
    String name;

    Employee(int id, String name) {
        this.id = id;
        this.name = name;
    }

    @Override
    public String toString() {
        return id + " - " + name;
    }
}

public class BinarySearchExample {
    public static void main(String[] args) {
        ArrayList<String> names = new ArrayList<>(Arrays.asList("Sagar", "Neha", "Amit", "Rita"));

        // Step 1: Sort the ArrayList
        Collections.sort(names);
        System.out.println("Sorted List: " + names);

        // Step 2: Binary search
        int index = Collections.binarySearch(names, "Neha");
        System.out.println("Index of Neha: " + index);

        // Searching for an element not present
        int notFound = Collections.binarySearch(names, "John");
        System.out.println("Index of John (not found): " + notFound);
    }
}

✅ Output:

Sorted List: [Amit, Neha, Rita, Sagar] Index of Neha: 1 Index of John (not found): -2

Note: -2 means the element would be inserted at index 1 if it existed.

3️⃣ Binary Search with Custom Objects

If you have an ArrayList:

ArrayList<Employee> empList = new ArrayList<>();
empList.add(new Employee(1, "Sagar"));
empList.add(new Employee(2, "Neha"));
empList.add(new Employee(3, "Amit"));

// Sort using Comparator (by name)
empList.sort(Comparator.comparing(emp -> emp.name));

// Binary search using Comparator
int index = Collections.binarySearch(empList, new Employee(0, "Neha"),
             Comparator.comparing(emp -> emp.name));

System.out.println("Index of Neha: " + index);

✅ Notes:

You must provide a Comparator if your ArrayList contains custom objects.

Sorting and Comparator used in binarySearch must match, otherwise results are unpredictable.