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
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
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
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
- and 2-arg parameterized constructor
- and 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 a 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
Related Articles:
- Byte Arrays sorting
- char Arrays sorting
- short Arrays sorting
- Integer Arrays sorting
- Float Arrays sorting
- Double Arrays sorting
- Long Arrays sorting
- String Arrays sorting
- How to Sort Arrays in Ascending and Descending order
- String Arrays sorting in ascending & descending order
- Sorting after merging two String[] Arrays
- Sorting Arrays using Comparable and Comparator interface
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 !!
