Searching element from Arrays using Binary Search Algorithm

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

 

Cautions:

  1. Arrays in all versions 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 primitive types from Natural-ordering of elements

Method signature:

public static int binarySearch(primitive[] pArray, primitive p);

SearchingPrimitiveFromNaturalSortingOfArrays.java

package in.bench.resources.java.collection;

import java.util.Arrays;

public class SearchingPrimitiveFromNaturalSortingOfArrays {

	public static void main(String[] args) {

		Integer[] intArrays = {31, 83, 53, 97, 29, 7, 13,  47, 79};
		String[] strArrays = {"James", "Bond", "Michael", 
				"Pups", "Jackson", "Bird"};

		System.out.println("Before sorting: Integer Arrays\n");

		// printing Integer Arrays
		System.out.println(Arrays.toString(intArrays));

		// sorting Arrays using
		Arrays.sort(intArrays);

		System.out.println("\nAfter sorting: Integer Arrays\n");

		// printing Integer Arrays
		System.out.println(Arrays.toString(intArrays));

		// binary search method
		int searchIntegerElement = Arrays.binarySearch(intArrays, 53);
		System.out.println("\nElement 53 is at index-position : "
				+ searchIntegerElement);

		System.out.println("\n\n\nBefore sorting: String Arrays\n");

		// printing Integer Arrays
		System.out.println(Arrays.toString(strArrays));

		// sorting Arrays using
		Arrays.sort(strArrays);

		System.out.println("\nAfter sorting: String Arrays\n");

		// printing Integer Arrays
		System.out.println(Arrays.toString(strArrays));

		// binary search method
		int searchStringElement = Arrays.binarySearch(strArrays,
				"James");
		System.out.println("\nElement James is at index-position : "
				+ searchStringElement);
	}
}

Output:

Before sorting: Integer Arrays

[31, 83, 53, 97, 29, 7, 13, 47, 79]

After sorting: Integer Arrays

[7, 13, 29, 31, 47, 53, 79, 83, 97]

Element 53 is at index-position : 5



Before sorting: String Arrays

[James, Bond, Michael, Pups, Jackson, Bird]

After sorting: String Arrays

[Bird, Bond, Jackson, James, Michael, Pups]

Element James is at index-position : 3

 

Case 2: Searching object types from Natural ordering of elements; using Comparable interface

Method signature:

public static int binarySearch(Object[] oArray, Object obj);

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 Arrays and
  • prints customer objects in ascending order of customer name
  • And searches customer from sorted Arrays of Customer type

SearchingObjectFromNaturalSortingOfArrays.java

package in.bench.resources.java.collection;

import java.util.Arrays;

public class SearchingObjectFromNaturalSortingOfArrays {

	public static void main(String[] args) {

		// creating Customer Arrays of initial size 4
		Customer[]  customers = new Customer[4];

		// initializing each customer objects
		customers[0] = new Customer(102, "Nandan Nilekeni");
		customers[1] = new Customer(104, "Shibulal");
		customers[2] = new Customer(101, "Narayan Murthy");
		customers[3] = new Customer(103, "Kris Gopalakrishnan");

		System.out.println("Before sorting: Customer Arrays\n");

		// printing Integer Arrays
		System.out.println(Arrays.toString(customers));

		// sorting Arrays using
		Arrays.sort(customers);

		System.out.println("\nAfter sorting: Customer Arrays"
				+ " according to ascending order of names\n");

		// printing Integer Arrays
		System.out.println(Arrays.toString(customers));

		// customer to be searched
		Customer searchCustomer = new Customer(101, "Narayan Murthy");

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

Output:

Before sorting: Customer Arrays

[[Id=102, Name=Nandan Nilekeni], [Id=104, Name=Shibulal], 
[Id=101, Name=Narayan Murthy], [Id=103, Name=Kris Gopalakrishnan]]

After sorting: Customer Arrays according to ascending order of names

[[Id=103, Name=Kris Gopalakrishnan], [Id=102, Name=Nandan Nilekeni], 
[Id=101, Name=Narayan Murthy], [Id=104, Name=Shibulal]]


Customer found at index position 2 from Sorted Arrays

 

Case 3: Searching object types from Customized ordering of elements; using Comparator interface

Method signature:

public static int binarySearch(Object[] oArray, Object obj, 
                                       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 natural 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 o1.customerId - o2.customerId;
	}
}

Main class

  • This class uses above customer POJO &
  • And customized sorting logic class implementing comparator interface to store objects inside Arrays
  • Then sorting according to comparator (i.e.; natural-ordering of customer Id)
  • prints customer objects in ascending order of customer Id
  • And searches customer from sorted Arrays of Customer type

SearchingObjectFromCustomizedSortingOfArrays.java

package in.bench.resources.java.collection;

import java.util.Arrays;

public class SearchingObjectFromCustomizedSortingOfArrays {

	public static void main(String[] args) {

		// creating Customer Arrays of initial size 4
		Customer[]  customers = new Customer[4];

		// initializing each customer objects
		customers[0] = new Customer(102, "Nandan Nilekeni");
		customers[1] = new Customer(104, "Shibulal");
		customers[2] = new Customer(101, "Narayan Murthy");
		customers[3] = new Customer(103, "Kris Gopalakrishnan");

		System.out.println("Before sorting: Customer Arrays\n");

		// printing Integer Arrays
		System.out.println(Arrays.toString(customers));

		// sorting Arrays using
		Arrays.sort(customers, new CustomerIdComparator());

		System.out.println("\nAfter sorting: Customer Arrays"
				+ " according to ascending order of Id\n");

		// printing Integer Arrays
		System.out.println(Arrays.toString(customers));

		// customer to be searched
		Customer searchCustomer = new Customer(104, "Shibulal");

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

Output:

Before sorting: Customer Arrays

[[Id=102, Name=Nandan Nilekeni], [Id=104, Name=Shibulal], 
[Id=101, Name=Narayan Murthy], [Id=103, Name=Kris Gopalakrishnan]]

After sorting: Customer Arrays according to ascending order of Id

[[Id=101, Name=Narayan Murthy], [Id=102, Name=Nandan Nilekeni], 
[Id=103, Name=Kris Gopalakrishnan], [Id=104, Name=Shibulal]]


Customer found at index position 3 from customized sorted Arrays

 

References:

 

Happy Coding !!
Happy Learning !!

Conversion of Arrays to List
Sorting Arrays using Comparable and Comparator