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 !!