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:
- Arrays in all versions of binarySearch() method has to be SORTED, otherwise binary search returns un-predictable or unexpected result
- Returns index-position of element upon successful searching
- Returns insertion-position of element upon unsuccessful searching
- 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:
- https://docs.oracle.com/javase/tutorial/collections/intro/
- https://docs.oracle.com/javase/tutorial/collections/interfaces/collection.html
- https://docs.oracle.com/javase/7/docs/api/java/util/Collection.html
- https://docs.oracle.com/javase/7/docs/api/java/util/Arrays.html
- https://docs.oracle.com/javase/tutorial/java/nutsandbolts/arrays.html
- https://docs.oracle.com/javase/7/docs/api/java/lang/reflect/Array.html
- https://docs.oracle.com/javase/specs/jls/se7/html/jls-10.html
Happy Coding !!
Happy Learning !!