Java Collections - binarySearch() Method

The java.util.Collections.binarySearch() method is used to search the specified list for the specified object using the binary search algorithm. The list must be sorted into ascending order according to the specified comparator (as by the sort(List, Comparator) method), prior to making this call. If it is not sorted, the results are undefined. If the list contains multiple elements equal to the specified object, there is no guarantee which one will be found.

Syntax

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

Here, T is the type of element in the list.

Parameters

Return Value

Returns the index of the search key, if it is contained in the list; otherwise, (-(insertion point) - 1). The insertion point is defined as the point at which the key would be inserted into the list: the index of the first element greater than the key, or list.size() if all elements in the list are less than the specified key. Note that this guarantees that the return value will be >= 0 if and only if the key is found.

Exception

Throws ClassCastException, if the list contains elements that are not mutually comparable using the specified comparator, or the search key is not mutually comparable with the elements of the list using this comparator.

Example:

In the example below, the java.util.Collections.binarySearch() method is used to search the given list for the given element.

import java.util.*;

public class MyClass {
  public static void main(String[] args) {
    //creating a List object
    List<Integer> MyList = new ArrayList<Integer>();

    //populating the list
    MyList.add(50);
    MyList.add(40);
    MyList.add(30);
    MyList.add(20);
    MyList.add(10);

    //creating a comparator for reverse order sorting
    Comparator<Integer> comp = Comparator.reverseOrder();

    //10 is present at index=4 (in reverse order)
    int idx1 = Collections.binarySearch(MyList, 10, comp);
    System.out.println(idx1);

    //45 is not present in the list. The insertion point of 45
    //will be 1 (in reverse order). hence, returns (-1-1) = -2
    int idx2 = Collections.binarySearch(MyList, 45, comp);
    System.out.println(idx2);
  }
}

The output of the above code will be:

4
-2