Perform Binary Search on ArrayList in Java

In this tutorial, you will learn how to perform binary search on ArrayList in Java.

1. Perform binary search on ArrayList using Collections.binarySearch()

In this example, we are performing binary search on the given ArrayList arrList. This list is unsorted, however in order to perform binary search the list must be sorted. Before performing binary search, we are sorting the ArrayList using Collections.sort() method.

Once the original list is sorted, we are using Collections.binarySearch() method. This method takes two arguments, the first argument is the list, on which we need to perform binary search and the second argument is the search item.

import java.util.ArrayList;
import java.util.Collections;
public class JavaExample {
  public static void main(String[] args)
  {
    ArrayList<Integer> arrList = new ArrayList<Integer>();
    //Adding element to arrList
    arrList.add(55);
    arrList.add(22);
    arrList.add(66);
    arrList.add(44);
    arrList.add(11);
    arrList.add(33);

    // We need to search this element using binary search
    int searchItem = 44;

    // Print arraylist elements
    System.out.println("Original ArrayList: "+arrList);

    //Sorting the original ArrayList to perform binary search
    Collections.sort(arrList);
    
    System.out.println("Sorted ArrayList: "+arrList);

    // Searching item using binarySearch() method
    int index = Collections.binarySearch(arrList,searchItem);

    if (index == -1)
      System.out.println("Element not found");
    else
      System.out.println("Element " + searchItem + " is found at "
              + "the index: " + index);
  }
}

Output:

Original ArrayList: [55, 22, 66, 44, 11, 33]
Sorted ArrayList: [11, 22, 33, 44, 55, 66]
Element 44 is found at the index: 3

2. Searching an element in ArrayList using iterative binary search

Here, we are demonstrating how to perform an iterative binary search on an ArrayList. The steps are as follows:
1. Compare the searchItem to the mid element. If it matches with the mid element, return the index of mid element, else proceed to next step.
2. Check if the searchItem is greater than mid element, if it is ignore the left side else ignore the right side.
3. Perform the step 1 and 2 on the left side or ride side depending on whether the searchItem is in left side or rightSide.
4. Repeat the steps from 1 to 3 until the element is found, if element is not found then return -1 as the element doesn’t exist in ArrayList.

import java.util.*;
public class JavaExample
{
  // This is a user defined method, it returns the index
  // of "searchItem". If searchItem is not present in the
  // ArrayList, it returns -1
  int binarySearchArrayList(ArrayList<Integer> arrList, int searchItem)
  {
    int leftSide = 0, rightSide = arrList.size() - 1;

    while (leftSide <= rightSide)
    {
      int mid = leftSide + (rightSide - leftSide) / 2;

      // Check if "searchItem" is the middle element
      if (arrList.get(mid) == searchItem)
        return mid;

      // If "searchItem" is greater than mid element then
      // ignore the left side as the arraylist is sorted and the
      // searchItem must be present in the rightSide.
      if (arrList.get(mid) < searchItem)
        leftSide = mid + 1;

        // If x is smaller, ignore right half
      else
        rightSide = mid - 1;
    }

    //element not found return -1
    return -1;
  }

  public static void main(String args[])
  {
    JavaExample obj = new JavaExample();
    ArrayList<Integer> arrList = new ArrayList<Integer>();
    arrList.add(11);
    arrList.add(22);
    arrList.add(33);
    arrList.add(44);
    arrList.add(55);
    arrList.add(66);

    //search this element
    int searchItem = 66;

    // Printing ArrayList
    System.out.println("ArrayList: "+arrList);

    //Performing binary search by calling user defined method
    int index = obj.binarySearchArrayList(arrList, searchItem);

    if (index == -1)
      System.out.println("Element not found");

    else
      System.out.println("Element " + searchItem + " is found at "
              + "the index: " + index);
  }
}

Output:

ArrayList: [11, 22, 33, 44, 55, 66]
Element 66 is found at the index: 5

Recommended Articles:

❮ Java Collections