Java ArrayList binary search example shows how to binary search Java ArrayList. The example also shows how to search ArrayList of custom class objects using Comparable or Comparator.
How to binary search ArrayList in Java?
You can binary search ArrayList using binarySearch method of the Collections class.
|
1 |
public static <T> int binarySearch(List<? extends Comparable<? super T>> list, T key) |
This method searches the list for the specified key using a binary search algorithm and returns the index of the key if it is found in the list.
If the key is not found, it returns -(x) - 1 value, where x is the insertion point where the key would be inserted. The insertion point is the index of the first element greater than the key or the size of the list if all elements of the list are less than the key specified. That means that we get return value >= 0 if and only if the element was found in the ArrayList.
Important note: ArrayList must be sorted in ascending order according to the natural order of its elements before calling the binarySearch method.
Java ArrayList binary search example
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
package com.javacodeexamples.collections.arraylist; import java.util.ArrayList; import java.util.Collections; public class ArrayListBinarySearchExample { public static void main(String[] args) { ArrayList<Integer> aListNumbers = new ArrayList<Integer>(); aListNumbers.add(7); aListNumbers.add(2); aListNumbers.add(9); aListNumbers.add(5); aListNumbers.add(8); System.out.println("Original ArrayList: " + aListNumbers); //ArrayList must be sorted before binary search Collections.sort(aListNumbers); System.out.println("Sorted ArrayList: " + aListNumbers); //binary search ArrayList int index = Collections.binarySearch(aListNumbers, 8); if(index >= 0) System.out.println("Element found at index: " + index); else System.out.println("Insertion point: " + index); } } |
Output
|
1 2 3 |
Original ArrayList: [7, 2, 9, 5, 8] Sorted ArrayList: [2, 5, 7, 8, 9] Element found at index: 3 |
If you re-run the code with 6 as the search value as given below,
|
1 2 |
//binary search ArrayList int index = Collections.binarySearch(aListNumbers, 6); |
You will get below given output.
|
1 2 3 |
Original ArrayList: [7, 2, 9, 5, 8] Sorted ArrayList: [2, 5, 7, 8, 9] Insertion point: -3 |
Why -3? It is because if you were to insert 6, it would be inserted at index 2 (i.e. between 5 and 7). If the element is not found, binarySearch method returns -(x) – 1 value where x is the insertion point. So it becomes -2 – 1 = -3.
How to search ArrayList containing objects of a custom class?
In the above example, ArrayList contained objects of the Integer class. Integer class implements Comparable interface so its objects can be compared with one another to order them in a natural order.
If you want to search ArrayList containing objects of a custom class, either the class must implement Comparable interface or you need to provide a custom Comparator while sorting and searching the ArrayList.
Below given example uses Comparable approach to search the ArrayList having objects of Employee class.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 |
package com.javacodeexamples.collections.arraylist; import java.util.ArrayList; import java.util.Collections; public class ArrayListBinarySearchExample { public static void main(String[] args) { //ArrayList of Employee objects ArrayList<Employee> aListEmployees = new ArrayList<Employee>(); aListEmployees.add(new Employee(35, "Alex")); aListEmployees.add(new Employee(24, "John")); aListEmployees.add(new Employee(29, "James")); System.out.println("Original ArrayList: " + aListEmployees); //sort ArrayList having Employee objects Collections.sort(aListEmployees); System.out.println("Sorted ArrayList: " + aListEmployees); //binary seach for employee having age of 35 and name Alex int index = Collections .binarySearch(aListEmployees, new Employee(35, "Alex")); if(index >= 0) System.out.println("Employee found at index: " + index); else System.out.println("Employee not found in ArrayList"); } } class Employee implements Comparable<Employee>{ private int empAge; private String empName; public Employee(){} public Employee(int empAge, String empName){ this.empAge = empAge; this.empName = empName; } public int getEmpAge() { return empAge; } public void setAge(int empAge) { this.empAge = empAge; } public String getEmpName() { return empName; } public void setEmpName(String empName) { this.empName = empName; } /* * This comapareTo method sorts the Employee * object according to employee age in * ascending order */ public int compareTo(Employee employee) { if(this.empAge > employee.empAge) return 1; else if(this.empAge < employee.empAge) return -1; else return 0; } public String toString(){ return empAge + ":" + empName; } } |
Output
|
1 2 3 |
Original ArrayList: [35:Alex, 24:John, 29:James] Sorted ArrayList: [24:John, 29:James, 35:Alex] Employee found at index: 2 |
You can also provide custom Comparator while sorting and searching the ArrayList. Check out how to sort ArrayList using Comparator.
Note 1: If ArrayList contains multiple elements equal to the specified search key, binarySearch method makes no guarantee on which element will be returned.
Note 2: If the ArrayList is not sorted before calling the binarySearch method, the result is undefined. Always make sure to sort the ArrayList before searching it for elements.
This example is a part of the ArrayList in Java Tutorial.
Please let me know your views in the comments section below.
About the author
- Gson – Serialize HashMap null entries - April 5, 2023
- Gson: Convert String to JsonObject without POJO - April 5, 2023
- Gson – Convert JSON to a Typed ArrayList - April 5, 2023
