How can I perform binary search on an ordered list

In this Q&A, we'll go over how to perform a binary search using java util methods.

Collections class provides two utility methods to perform binarySearch with and without a Comparator.

Binary search performance on an ArrayList is O(log n).  For LinkedList, the performance is O(n) traversals with O(log n) compares

Note that the behavior is undefined if the collection is an unordered collection.  Here's a code snippet:

List<Integer> al = Arrays.asList( 0,1,2,3,10,20,31,62);

idx  = Collections.binarySearch(al, 10);

assert(idx == 4 );

Arrays class also has utility methods to perform binarySearch.  Performance is O(log n).  Here's a code snippet:

int[] arr = {0,1,2,3,10,20,31,62};

int idx  = Arrays.binarySearch(arr, 10);

assert(idx == 4 );