With this example we are going to demonstrate how to Binary search a List. We will use the binarySearch(List list, T key) API method of the Collections class. Collections provides static methods that operate on or return collections. The ArrayList is used as a List implementation, but the same API applies to any type of List implementation classes e.g. Vector etc. In short, to Binary search a List you should:
- Create a new ArrayList.
- Populate the list with elements, with the
add(E e)API method of the ArrayList. - Invoke the
sort(ListAPI method of Collections, in order to sort the list before searching it.list) - Invoke the
binarySearch(List list, T key)API method of Collections. It searches the provided list for the specified value using the binary search algorithm. It returns the index of the search value, if it is contained in the List, otherwise it returns (-(insertion point) – 1). The insertion point is defined as the point at which the value would be inserted into the array.
Let’s take a look at the code snippet that follows:
package com.javacodegeeks.snippets.core;
import java.util.ArrayList;
import java.util.Collections;
public class BinarySearchArrayList {
public static void main(String[] args) {
/*
Please note that the same API applies to any type of
List implementation classes e.g. Vector etc
*/
// Create an ArrayList and populate it with elements
ArrayList arrayList = new ArrayList();
arrayList.add("element_1");
arrayList.add("element_4");
arrayList.add("element_2");
arrayList.add("element_5");
arrayList.add("element_3");
/*
static int binarySearch(List list, Object element) operation searches the provided
List for the specified value using the binary search algorithm. Beware the source List
must be sorted before it can be searched using this method. The method returns
the index of the search value, if it is contained in the List; otherwise,
(-(insertion point) - 1). The insertion point is defined as the point at which
the value would be inserted into the array
*/
Collections.sort(arrayList);
// We search for a value that exists in the List (value element_2)
int searchIndex1 = Collections.binarySearch(arrayList,"element_2");
System.out.println("Value element_2 found at index : " + searchIndex1);
// We search for a value that does not exist in the array (value element_6)
int searchIndex2 = Collections.binarySearch(arrayList,"element_6");
System.out.println("Value element_6 should be inserted at index : " + (-(searchIndex2) - 1));
}
}
Output:
Value element_2 found at index : 1
Value element_6 should be inserted at index : 5
This was an example of how to Binary search a List in Java.
