How to Use Collections.binarySearch in Java: Simple Guide

Use Collections.binarySearch to find the index of an element in a sorted List. It returns the element's index if found, or a negative value indicating the insertion point if not found. The list must be sorted before calling this method.

Syntax

The basic syntax of Collections.binarySearch is:

• Collections.binarySearch(List<T> list, T key): Searches for key in the sorted list.
• Collections.binarySearch(List<T> list, T key, Comparator<? super T> c): Searches using a custom Comparator.

The method returns the index of the search key if it is contained in the list; otherwise, it returns (-insertion_point - 1), where insertion_point is the index where the key would be inserted to keep the list sorted.

java

int index = Collections.binarySearch(list, key);
int indexWithComparator = Collections.binarySearch(list, key, comparator);

Example

This example shows how to use Collections.binarySearch to find an element in a sorted list of integers.

java

import java.util.*;

public class BinarySearchExample {
    public static void main(String[] args) {
        List<Integer> numbers = Arrays.asList(10, 20, 30, 40, 50);
        // The list must be sorted for binarySearch to work correctly
        int key = 30;
        int index = Collections.binarySearch(numbers, key);

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

        int missingKey = 35;
        int missingIndex = Collections.binarySearch(numbers, missingKey);
        System.out.println("Index of " + missingKey + ": " + missingIndex);
    }
}

Output

Index of 30: 2
Index of 35: -4

Common Pitfalls

• List must be sorted: If the list is not sorted, the result is undefined and likely incorrect.
• Return value interpretation: A negative return value means the key was not found; use -returnValue - 1 to find the insertion point.
• Using wrong comparator: When using a custom comparator, ensure it matches the list's sorting order.

java

import java.util.*;

public class PitfallExample {
    public static void main(String[] args) {
        List<Integer> unsorted = new ArrayList<>(Arrays.asList(50, 10, 40, 20, 30));
        int key = 20;
        // Wrong: list is not sorted
        int wrongIndex = Collections.binarySearch(unsorted, key);
        System.out.println("Wrong index (unsorted list): " + wrongIndex);

        // Correct: sort the list first
        Collections.sort(unsorted);
        int correctIndex = Collections.binarySearch(unsorted, key);
        System.out.println("Correct index (sorted list): " + correctIndex);
    }
}

Output

Wrong index (unsorted list): -2
Correct index (sorted list): 1

Quick Reference

Key points to remember:

• Input list must be sorted.
• Returns index if found.
• Returns negative insertion point if not found.
• Use custom comparator for non-natural ordering.

Key Takeaways

Always sort the list before using Collections.binarySearch.

The method returns the index if the element is found, otherwise a negative insertion point.

Use a custom Comparator if your list uses a special order.

Interpret negative results carefully to find where to insert missing elements.

Collections.binarySearch works only on Lists, not arrays directly.