Home » Core Java » util » Collections » Binary search List example

About Byron Kiourtzoglou

Avatar photo
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.

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.

Do you want to know how to develop your skillset to become a Java Rockstar?

Subscribe to our newsletter to start Rocking right now!

To get you started we give you our best selling eBooks for FREE!

 

1. JPA Mini Book

2. JVM Troubleshooting Guide

3. JUnit Tutorial for Unit Testing

4. Java Annotations Tutorial

5. Java Interview Questions

6. Spring Interview Questions

7. Android UI Design

 

and many more ....

 

Receive Java & Developer job alerts in your Area

I have read and agree to the terms & conditions

 

Subscribe
Notify of
guest

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

0 Comments
Inline Feedbacks
View all comments