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 natural ordering of its elements (as by the sort(List) 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 Comparable<? super T>> list, 
                                    T key)

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 (for example, strings and integers), or the search key is not mutually comparable with the elements of the list.

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(10);
    MyList.add(20);
    MyList.add(30);
    MyList.add(40);
    MyList.add(50);

    //30 is present at index=2
    System.out.println(Collections.binarySearch(MyList, 30));

    //35 is not present in the list. The insertion point
    //of 35 will be 3. hence, returns (-3-1) = -4
    System.out.println(Collections.binarySearch(MyList, 35));  
  }
}

The output of the above code will be:

2
-4