Collections

Binary search List example

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(List list) API method of Collections, in order to sort the list before searching it.
  • 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.

Byron Kiourtzoglou

Byron is a master software engineer working in the IT and Telecom domains. He is an applications developer in a wide variety of applications/services. He is currently acting as the team leader and technical architect for a proprietary service creation and integration platform for both the IT and Telecom industries in addition to a in-house big data real-time analytics solution. He is always fascinated by SOA, middleware services and mobile development. Byron is co-founder and Executive Editor at Java Code Geeks.
Subscribe
Notify of
guest

This site uses Akismet to reduce spam. Learn how your comment data is processed.

0 Comments
Oldest
Newest Most Voted
Inline Feedbacks
View all comments
Back to top button