BeginnersBook

  • Home
  • Java
    • Java OOPs
    • Java Collections
    • Java Examples
  • C
    • C Examples
  • C++
    • C++ Examples
  • DBMS
  • Computer Network
  • Python
    • Python Examples
  • More…
    • jQuery
    • Kotlin
    • WordPress
    • SEO
    • JSON
    • JSP
    • JSTL
    • Servlet
    • MongoDB
    • XML
    • Perl

Perform Binary Search on ArrayList in Java

By Chaitanya Singh | Filed Under: 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:

  • Add multiple items to an ArrayList
  • Clone an ArrayList
  • Get sublist of an ArrayList
❮ Java Collections

Java Tutorial

Java Introduction

  • Java Index
  • Java Introduction
  • History of Java
  • Features of Java
  • C++ vs Java
  • JDK vs JRE vs JVM
  • JVM - Java Virtual Machine
  • First Java Program
  • Variables
  • Data Types
  • Operators

Java Flow Control

  • Java If-else
  • Java Switch-Case
  • Java For loop
  • Java while loop
  • Java do-while loop
  • Continue statement
  • break statement

Java Arrays

  • Java Arrays

OOPs Concepts

  • OOPs Concepts
  • Constructor
  • Java String
  • Static keyword
  • Inheritance
  • Types of inheritance
  • Aggregation
  • Association
  • Super Keyword
  • Method overloading
  • Method overriding
  • Overloading vs Overriding
  • Polymorphism
  • Types of polymorphism
  • Static and dynamic binding
  • Abstract class and methods
  • Interface
  • Abstract class vs interface
  • Encapsulation
  • Packages
  • Access modifiers
  • Garbage Collection
  • Inner classes
  • Static import
  • Static constructor

Java Exception Handling

  • Exception handling
  • Java try-catch
  • Java throw
  • Java throws
  • Checked and Unchecked Exceptions
  • Jav try catch finally
  • Exception Examples
  • Exception Propagation

Collections Framework

  • Collections in Java
  • Java ArrayList
  • Java LinkedList
  • Java Vector
  • Java HashSet
  • Java LinkedHashSet
  • Java TreeSet
  • Java HashMap
  • Java TreeMap
  • Java LinkedHashMap
  • Java Queue
  • Java PriorityQueue
  • Java Deque
  • Comparable interface
  • Comparator interface
  • Collections Interview Questions

MORE ...

  • Java Scanner Class
  • Java 8 Features
  • Java 9 Features
  • Java Conversion
  • Java Date
  • Java Multithreading
  • Java I/O
  • Java Serialization
  • Java Regex
  • Java AWT
  • Java Swing
  • Java Enum
  • Java Annotations
  • Java main method
  • Java Interview Q

Copyright © 2012 – 2022 BeginnersBook . Privacy Policy . Sitemap