The ArrayList class is a part of the collection framework and is present in java.util package. It provides us with resizable or dynamic arrays in java. It is quite slower than standard arrays but can be helpful in some programs where we need to come up with cleaner and shorter code and lots of manipulation of an array is needed.
The most effective algorithm to search an element in a sorted array is the binary-search algorithm. In this article, we are going to implement this using the Java ArrayList.
Approaches:
There are three ways to implement binary search on java ArrayList which are listed below briefing the concept followed by a java example for the implementation part.
- Iterative Binary Search (Normal Binary Search Using Loop)
- Recursive Binary Search (Binary Search Using Recursion)
- Using the built-in binarySearch method of java collections.
Method 1: Iterative Binary Search
In this approach, we ignore half of the elements after one comparison. As the array is sorted.
- Compare the given value to be searched with the middle element.
- If it matches with the middle element we return x.
- If it is greater than the middle element then do the same for the right subarray .ie. the size of the array is reduced to half and the array we are left with to compare is the right subarray.
- If it is less than the middle element then do the same for the left subarray .ie. the size of the array is reduced to half and the array we are left with to compare is the left subarray.
- If we do not return anything but our search ends, then return -1, it implies that the element is not present in that array.
Java
// Java program to print binary search over an ArrayListimport java.io.*;import java.util.*;class BinarySearch{ // Returns index of x if it is present in arr[], // else return -1 int binarySearch(ArrayList<Integer> arr, int x) { int left = 0, right = arr.size() - 1; while (left <= right) { int mid = left + (right - left) / 2; // Check if x is present at mid if (arr.get(mid) == x) return mid; // If x greater, ignore left half if (arr.get(mid) < x) left = mid + 1; // If x is smaller, ignore right half else right = mid - 1; } // if we reach here, then element was // not present return -1; } // Driver method to test above public static void main(String args[]) { BinarySearch ob = new BinarySearch(); ArrayList<Integer> arr = new ArrayList<Integer>(); arr.add(5); arr.add(10); arr.add(15); arr.add(20); arr.add(25); arr.add(30); arr.add(35); int x = 10; // Printing elements of array list System.out.println("The elements of the arraylist are: "+arr); int result = ob.binarySearch(arr, x); if (result == -1) System.out.println("Element not present"); else System.out.println("The Element " + x + " is found at " + "index " + result); }} |
The elements of the arraylist are: [5, 10, 15, 20, 25, 30, 35] The Element 10 is found at index 1
Method 2: Recursive Binary Search
- Compare the element t be searched (x) with the middle element.
- If x matches with the middle element, we return the mid index.
- Else If x is greater than the mid element, then x can only lie in the right half subarray after the mid element. So we recur for the right half.
- Else (x is smaller) recur for the left half.
Java
// Java implementation of recursive Binary Searchimport java.io.*;import java.util.*;class BinarySearch{ // Returns index of x if it is present in arr[l.. // r], else return -1 int binarySearch(ArrayList<Integer> arr, int l, int r, int x) { if (r >= l) { int mid = l + (r - l) / 2; // If the element is present at the // middle itself if (arr.get(mid) == x) return mid; // If element is smaller than mid, then // it can only be present in left subarray if (arr.get(mid) > x) return binarySearch(arr, l, mid - 1, x); // Else the element can only be present // in right subarray return binarySearch(arr, mid + 1, r, x); } // We reach here when element is not present // in array return -1; } // Driver method to test above public static void main(String args[]) { BinarySearch ob = new BinarySearch(); ArrayList<Integer> arr = new ArrayList<Integer>(); arr.add(5); arr.add(10); arr.add(15); arr.add(20); arr.add(25); arr.add(30); arr.add(35); int n = arr.size(); // We will find x inside the arraylist int x = 10; // Printing elements of array list System.out.println("The elements of the arraylist are: "+arr); int result = ob.binarySearch(arr,0,n-1,x); if (result == -1) System.out.println("Element not present"); else System.out.println("The Element " + x + " is found at " + "index " + result); }} |
The elements of the arraylist are: [5, 10, 15, 20, 25, 30, 35] The Element 10 is found at index 1
Method 3: Using the built-in binarySearch method of Collections Class
In this method, we just call the binarySearch() method of collections framework and parse our sorted ArrayList and the value to be searched into the method, This will return the index of the element if present and -1 otherwise.
Java
// Java program to demonstrate the searching of// an element in ArrayList using binarySearch()// of Collections classimport java.util.ArrayList;import java.util.Collections;public class BinarySearch { public static void main(String[] args) { ArrayList<Integer> arr = new ArrayList<Integer>(); arr.add(5); arr.add(10); arr.add(15); arr.add(20); arr.add(25); arr.add(30); arr.add(35); // Initializing the key to be found. int val = 10; // Printing elements of array list System.out.println("The elements of the arraylist are: "+arr); // Implementing the built-in binarySearch method from collections int result = Collections.binarySearch(arr,val); if (result == -1) System.out.println("Element not present"); else System.out.println("The Element " + val + " is found at " + "index " + result); }} |
The elements of the arraylist are: [5, 10, 15, 20, 25, 30, 35] The Element 10 is found at index 1
Time complexity: O(logn)
Auxiliary space: O(1) as it is using constant variables
