How to Use Collections.binarySearch() in Java

 When working with sorted collections in Java, the Collections.binarySearch() method can be a helpful tool for quickly finding the position of an object in the collection. Here's a closer look at how to use this method effectively.

Syntax of Collections.binarySearch()

Before diving into code examples, it's important to understand the syntax of Collections.binarySearch(). The method takes two arguments:

• A sorted list of objects to search
• The object to search for

It returns the index of the object in the list, or a negative number if the object is not found. Specifically, if the object is not present in the list, it returns the negation of the insertion point - 1. For example, if the object would be inserted at index 3, the method returns -4.

Example Usage of Collections.binarySearch()

Here's a simple example that demonstrates how to use Collections.binarySearch() to search for an integer in a sorted list:

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

public class BinarySearchExample {
    public static void main(String[] args) {
        List<Integer> numbers = new ArrayList<>();
        numbers.add(1);
        numbers.add(3);
        numbers.add(5);
        numbers.add(7);
        numbers.add(9);

        int index = Collections.binarySearch(numbers, 5);
        System.out.println("Index of 5: " + index); // Output: 2

        index = Collections.binarySearch(numbers, 8);
        System.out.println("Index of 8: " + index); // Output: -5
    }
}

In this example, we create a new ArrayList of integers and populate it with odd numbers up to 9. Then, we use Collections.binarySearch() to search for the value 5 and 8. We print out the resulting index or negative number.

Important Points to Keep in Mind

There are a few important things to keep in mind when using Collections.binarySearch():

• The list must be sorted in ascending order for the method to work properly.
• If the list contains duplicates, there is no guarantee which one will be found.
• If the object is not present in the list, the method returns the negation of the insertion point - 1.
• Collections.binarySearch() works with objects collections like ArrayList and LinkedList.
• The point must either implement Comparable or we must provide an object of the class that implements the Comparator.
• The method does not take any range parameters like Arrays.binarySearch() does.
• For ArrayList, the time complexity of the method is O(log n) for O(log n) object comparisons because of direct access. For LinkedList, it will be O(n) for O(log n) object comparisons because the middle point needs to be found, which takes linear time in a linked list.

By keeping these points in mind and using Collections.binarySearch() correctly, you can quickly and efficiently search for objects in a sorted collection.