Collections.binarySearch() in Java

 

The Collections.binarySearch() method is a part of the java.util.Collections class, which is used to search for the position of an object in a sorted list. If the key is not found, it returns "-(insertion_point + 1)". The insertion point is the index at which the key would be inserted into the list to maintain its sorted order.

Here's an example of how to use Collections.binarySearch() to search for an integer key in a list sorted in ascending order:

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

public class Example {
    public static void main(String[] args) {
        List<Integer> list = new ArrayList<>();
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(10);
        list.add(20);

        // 10 is present at index 3.
        int index = Collections.binarySearch(list, 10);
        System.out.println(index); // output: 3

        // 13 is not present. 13 would have been inserted
        // at position 4. So the function returns -(4 + 1) = -5.
        index = Collections.binarySearch(list, 13);
        System.out.println(index); // output: -5
    }
}

• Some important points to keep in mind when using Collections.binarySearch() and Arrays.binarySearch() are:
• Unlike Arrays.binarySearch(), Collections.binarySearch() does not take any range arguments. It simply takes the element to be searched.
• The input list must be sorted for Collections.binarySearch() to work correctly. If the list is not sorted, the results are undefined.
• If there are duplicates in the list, Collections.binarySearch() does not guarantee which one will be found.
• Arrays.binarySearch() works for arrays, including arrays of primitive data types, while Collections.binarySearch() works for objects that implement the Collection interface, such as ArrayList and LinkedList.
• The List or any other Collection must only contain non-primitive types.
• The elements of the list must implement the Comparable interface or we must provide an object of a class that implements the Comparator interface.
• If Collections.binarySearch() is used with an ArrayList, then the time complexity will be O(log n) for O(log n) object comparisons due to direct access. However, performing binary search on a LinkedList will take O(n) for O(log n) object comparisons because the middle point needs to be found, which takes linear time in a linked list.
• There are two binarySearch method declarations in the Collections class and multiple binarySearch method declarations in the Arrays class.