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:
- The specified list in both the version 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 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:
- 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/tutorial/collections/interfaces/list.html
- https://docs.oracle.com/javase/7/docs/api/java/util/List.html
- https://docs.oracle.com/javase/tutorial/collections/interfaces/order.html
- https://docs.oracle.com/javase/7/docs/api/java/util/Collections.html
Happy Coding !!
Happy Learning !!