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