Searching element from ArrayList using Binary Search Algorithm

In this article, we will discuss how to search an elements from List using Collections class’s utility binarySearch() method which uses Binary Search algorithm

Cautions:

  1. The specified list in both the version of binarySearch() method has to be SORTED, otherwise binary search returns un-predictable or unexpected result
  2. Returns index-position of element upon successful searching
  3. Returns insertion-position of element upon unsuccessful searching
  4. If Comparator version of binarySearch() method is used, then compulsorily same comparator object has to be passed while searching; otherwise binary search returns un-predictable or unexpected result

 

Case 1: Searching from Default Natural ordering of elements of String type

Method signature:

public static int binarySearch(List<String> list, Object o);

SearchingFromDefaultSortingOfArrayList.java

package in.bench.resources.java.collection;

import java.util.ArrayList;
import java.util.Collections;

public class SearchingFromDefaultSortingOfArrayList {

	public static void main(String[] args) {

		// creating ArrayList object of type String
		ArrayList<String> al = new ArrayList<String>();

		// adding elements to ArrayList object
		al.add("Narayan Murthy");
		al.add("Dinesh");  
		al.add("Nandan Nilekeni");  
		al.add("Ashok Arora");
		al.add("Shibulal");
		al.add("Kris Gopalakrishnan");
		al.add("Raghavan");

		System.out.println("Before Sorting:"
				+ " Iterating ArrayList values\n");

		// Iterating using enhanced for-loop
		for(String str : al){
			System.out.println(str);
		}

		// sorting using Collections.sort(al);
		Collections.sort(al);

		System.out.println("\n\nAfter Sorting:"
				+ " Iterating ArrayList values\n");

		// Iterating using enhanced for-loop
		for(String str : al){
			System.out.println(str);
		}

		// searching element from default natural ordering
		// of String type
		int iStringSearch = Collections
				.binarySearch(al, "Kris Gopalakrishnan");
		System.out.println("\n\nElement found at index position "
				+ iStringSearch 
				+ " from Sorted ArrayList");
	}
}

Output:

Before Sorting: Iterating ArrayList values

Narayan Murthy
Dinesh
Nandan Nilekeni
Ashok Arora
Shibulal
Kris Gopalakrishnan
Raghavan


After Sorting: Iterating ArrayList values

Ashok Arora
Dinesh
Kris Gopalakrishnan
Nandan Nilekeni
Narayan Murthy
Raghavan
Shibulal


Element found at index position 2 from Sorted ArrayList

 

Case 2: Searching from Natural ordering of elements of Object type

Method signature:

public static int binarySearch(List<String> list, Object o);

Customer.java

  • Customer POJO with 2 member variables of Integer and String type
  • which implements Comparable interface to provide natural ordering of Customer objects on the basis of customer name
package in.bench.resources.java.collection;

public class Customer implements Comparable<Customer> {

	// member variables
	int customerId;
	String customerName;

	// 2-arg parameterized constructor
	public Customer(int customerId, String customerName) {
		super();
		this.customerId = customerId;
		this.customerName = customerName;
	}

	// override toString() method
	@Override
	public String toString() {
		return "Customer ["
				+ "customerId=" + customerId
				+ ", customerName=" + customerName 
				+ "]";
	}

	// override compareTo() method
	@Override
	public int compareTo(Customer o) {
		return this.customerName.compareTo(o.customerName);
	}
}

Main class

  • This class uses above customer POJO to store objects inside ArrayList and
  • prints customer objects in ascending order of customer name
  • And searches customer from sorted ArrayList of Customer type

SearchingFromNaturalSortingOfArrayList.java

package in.bench.resources.java.collection;

import java.util.ArrayList;
import java.util.Collections;

public class SearchingFromNaturalSortingOfArrayList {

	public static void main(String[] args) {

		// creating ArrayList object of type Customer
		ArrayList<Customer> al = new ArrayList<Customer>();

		// adding elements to ArrayList object
		al.add(new Customer(101, "Narayan Murthy"));
		al.add(new Customer(107, "Dinesh"));
		al.add(new Customer(103, "Nandan Nilekeni"));
		al.add(new Customer(102, "Ashok Arora"));
		al.add(new Customer(104, "Shibulal"));
		al.add(new Customer(106, "Kris Gopalakrishnan"));
		al.add(new Customer(105, "Raghavan"));

		System.out.println("Before Sorting:"
				+ " Insertion Order\n");

		// insertion order
		for(Customer cust : al){
			System.out.println(cust.customerId 
					+ "  " 
					+ cust.customerName);
		}

		// sorting using Collections.sort(al);
		Collections.sort(al);

		System.out.println("\n\nAfter Sorting:"
				+ " Natural ordering of Customer Name\n");

		// natural ordering of customer name using Comparable
		for(Customer cust : al){
			System.out.println(cust.customerId 
					+ "  " 
					+ cust.customerName);
		}

		// customer to be searched
		Customer searchCustomer = new Customer(105, "Raghavan");

		// searching element from default natural ordering 
		// of String type
		int iStringSearch = Collections
				.binarySearch(al, searchCustomer);
		System.out.println("\n\nCustomer found at index position "
				+ iStringSearch 
				+ " from Sorted ArrayList");
	}
}

Output:

Before Sorting: Insertion Order

101  Narayan Murthy
107  Dinesh
103  Nandan Nilekeni
102  Ashok Arora
104  Shibulal
106  Kris Gopalakrishnan
105  Raghavan


After Sorting: Natural ordering of Customer Name

102  Ashok Arora
107  Dinesh
106  Kris Gopalakrishnan
103  Nandan Nilekeni
101  Narayan Murthy
105  Raghavan
104  Shibulal


Customer found at index position 5 from Sorted ArrayList

 

Case 3: Searching from Customized ordering of elements of Object type

Method signature:

public static int binarySearch(
		List<Object> list, 
		Object o, 
		Comparator<Object>  c);

Customer.java

  • Customer POJO with 2 member variables of Integer and String type
  • 2-arg constructor
  • Overriding toString() method
package in.bench.resources.java.collection;

public class Customer {

	// member variables
	int customerId;
	String customerName;

	// 2-arg parameterized constructor
	public Customer(int customerId, String customerName) {
		super();
		this.customerId = customerId;
		this.customerName = customerName;
	}

	// override toString() method
	@Override
	public String toString() {
		return "Customer ["
				+ "customerId=" + customerId 
				+ ", customerName=" + customerName
				+ "]";
	}
}

CustomerIdComparator.java

  • This is separate class which implements Comparator interface providing customized sorting logic
  • compare() method provides reverse order sorting logic, according to customer Id
package in.bench.resources.java.collection;

import java.util.Comparator;

public class CustomerIdComparator implements Comparator<Customer> {

	@Override
	public int compare(Customer o1, Customer o2) {
		return o2.customerId - o1.customerId;
	}
}

Main class

  • This class uses above customer POJO and customized sorting logic class
  • implementing comparator interface, to store objects inside ArrayList
  • sorting according to comparator (i.e.; reverse ordering of customer Id)
  • prints customer objects in descending order of customer Id
  • And searches customer from sorted ArrayList of Customer type

SearchingFromCustomizedSortingOfArrayList.java

package in.bench.resources.java.collection;

import java.util.ArrayList;
import java.util.Collections;

public class SearchingFromCustomizedSortingOfArrayList {

	public static void main(String[] args) {

		// creating ArrayList object of type Customer
		ArrayList<Customer> al = new ArrayList<Customer>();

		// adding elements to ArrayList object
		al.add(new Customer(101, "Narayan Murthy"));
		al.add(new Customer(107, "Dinesh"));
		al.add(new Customer(103, "Nandan Nilekeni"));
		al.add(new Customer(102, "Ashok Arora"));
		al.add(new Customer(104, "Shibulal"));
		al.add(new Customer(106, "Kris Gopalakrishnan"));
		al.add(new Customer(105, "Raghavan"));

		System.out.println("Before Sorting:"
				+ " Insertion Order\n");

		// insertion order
		for(Customer cust : al){
			System.out.println(cust.customerId 
					+ "  " 
					+ cust.customerName);
		}

		// sorting using Collections.sort(al, comparator);
		Collections.sort(al, new CustomerIdComparator());

		System.out.println("\n\nAfter Sorting:"
				+ " Reverse ordering of Customer Id\n");

		// reverse ordering of customer Id using Comparator
		for(Customer cust : al){
			System.out.println(cust.customerId 
					+ "  " 
					+ cust.customerName);
		}

		// customer to be searched
		Customer searchCustomer = new Customer(102, "Ashok Arora");

		// searching element from default natural ordering 
		// of String type
		int iStringSearch = Collections
				.binarySearch(al, searchCustomer, 
						new CustomerIdComparator());
		System.out.println("\n\nCustomer found at index position " 
				+ iStringSearch 
				+ " from customized sorted ArrayList");
	}
}

Output:

Before Sorting: Insertion Order

101  Narayan Murthy
107  Dinesh
103  Nandan Nilekeni
102  Ashok Arora
104  Shibulal
106  Kris Gopalakrishnan
105  Raghavan


After Sorting: Reverse ordering of Customer Id

107  Dinesh
106  Kris Gopalakrishnan
105  Raghavan
104  Shibulal
103  Nandan Nilekeni
102  Ashok Arora
101  Narayan Murthy


Customer found at index position 5 from customized sorted ArrayList

 

References:

 

Happy Coding !!
Happy Learning !!

How to Reverse order of elements in ArrayList
Sorting ArrayList using Comparable and Comparator