Collections

Java ArrayList binary search example

Java ArrayList binary search example shows how to binary search Java ArrayList. Example also shows how to binary search ArrayList of custom class objects using Comparable/Comparator.

How to binary search ArrayList in Java?

You can binary search ArrayList using binarySearch method of Collections class.

This method searches the list for specified key using 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. 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 binarySearch method.

Java ArrayList binary search example

Output

If you re-run the code with 6 as the search value as given below,

You will get below given output.

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 element is not found, binarySearch method returns -(x) – 1 value where x is the insertion point. So it becomes -2 – 1 = -3.

How to binary search ArrayList containing objects of custom class?

In above example, ArrayList contained objects of Integer class. Integer class implements Comparable interface so its objects can be compared with one another to order them in natural order.

If you want to binary 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 binary searching the ArrayList.

Below given example uses Comparable approach to binary search the ArrayList having objects of Employee class.

Output

You can also provide custom Comparator while sorting and searching 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 invoking binarySearch method, result is undefined. Always make sure to sort the ArrayList before binary search it for elements.

Please let us know your views in the comments section below.

Join 1000+ fellow learners! Enter your email address below: