Java’s Binary Search API in Five Minutes

    Jackie Ng
    Jackie Ng
    Share

    Binary search is a very efficient search algorithm that finds an item in a sorted array by repeatedly cutting down the search range by half. As a result, run time is logarithmic, or O(log n). This post teaches you how to use Java’s Arrays.binarySearch and Collections.binarySearch for searching sorted arrays or array lists considerably faster than you could using the linear search methods like a for loop or List.contains.

    At a minimum, only working knowledge of arrays and lists is required. Knowing about Comparable and Comparator comes in handy.

    Searching with Binary Search

    Java’s binary search function can be found in java.util.Arrays and java.util.Collections APIs. The Arrays API provides the implementation for arrays.

    Searching an Array

    In its simplest form, the static method Arrays.binarySearch takes an array of any primitive type (as well as Object or reference type) and a search key, for examples:

    The methods return an int representing the index of the found search key within the array, or otherwise a negative value (whose significance I’ll explain in a moment) if it is not found.

    Here’s a code example:

    int[] numbers = {2, 3, 5, 7};
    System.out.println("index of 5 is "
            + Arrays.binarySearch(numbers, 5));
    // index of 5 is 2
    

    Before you use the binary search function, make sure the array is already sorted into ascending order (for example, with the Arrays.sort method), otherwise the results will be unexpected.

    Searching a Range

    If you are supposed to only search a range of the specified array for the search key, you can use this overload:

    Note that the toIndex is exclusive to be searched. With the preceding example, if you want to only search the array from index 0 up to 2 (inclusive), you write:

    Arrays.binarySearch(numbers, 0, 3, 5);
    

    Searching with a Comparator

    If you are using the binary search method for an Object array, the elements of the array must either implement the Comparable interface or a Comparator must be specified:

    The Comparator object is used by the binary search to compare the ordering of two objects so that it can determine whether an object comes before or after the other within the array during the search. In other words, the APIs do not limit an Object array to ascending/ natural order.

    The array can be in any sort order as long as you can provide a Comparator which imposes an ordering consistent to the array’s sort order. In the simplest case, you have used the same comparator to sort the array with Arrays.sort(T[] a, Comparator<? super T> c).

    Here’s an example to search an Integer array in descending order:

    Integer[] numbers = {2, 3, 5, 7};
    // sort numbers into reverse natural order, i.e. {7, 5, 3, 2}
    Arrays.sort(numbers, Collections.reverseOrder());
    
    // search using a reverse natural order comparator
    System.out.println("index of 5 is " +
            Arrays.binarySearch(numbers, 5, Collections.reverseOrder()));
    // index of 5 is 1
    

    Searching a List

    The Java’s Collections class, on the other hand, provides the binary search function for operating on Lists. The two versions of the overloaded Collections.binarySearch method are:

    The usage of these methods are similar to Arrays.binarySearch except the methods take a List of objects rather than an array.

    Here’s an example:

    List<Integer> numbers = Arrays.asList(2, 3, 5, 7);
    System.out.println("index of 5 is "
            + Collections.binarySearch(numbers, 5));
    // index of 5 is 2
    

    Caveat: It is unwise to use binary search on a LinkedList whose implementation only allows sequential access to its elements, causing the binary search algorithm to perform very poorly.

    Binary Search for Insertion

    The APIs of both Arrays.binarySearch and Collections.binarySearch have a special behavior when they couldn’t find the given search key in the specified array or list: In that case the binary search method in both classes returns a negative value that is equivalent to - <insertion point> - 1, where insertion point is defined as the index at which the search key would be inserted into the array or list.

    Here’s an example:

    List<Integer> numbers = new ArrayList<>(
            Arrays.asList( 2, 3, 5, 7, 11, 13, 17, 19, 23, 29));
    
    System.out.println("index of 5 is "
            + Collections.binarySearch(numbers, 5));
    System.out.println("index of 23 is "
            + Collections.binarySearch(numbers, 23));
    System.out.println("index of 9 is "
            + Collections.binarySearch(numbers, 9));
    System.out.println("index of 31 is "
            + Collections.binarySearch(numbers, 31));
    

    The output:

    index of 5 is 2
    index of 23 is 8
    index of 9 is -5
    index of 31 is -11
    

    In this example, integers 9 and 31 do not exist in the list. With the returned negative value, 9 would have been inserted at index 4, pushing the original entries at indices 4 and after one slot backward. The value of 31 would have been inserted at index 10, which is at the end of the list. If we were to insert 9 into the list, we could write code like this:

    int pos = Collections.binarySearch(numbers, 9);
    if (pos < 0) {
        numbers.add(Math.abs(pos)-1, 9);
    }
    

    This feature of binary search is particularly useful for implementing the insertion function for some sort of priority queue for example, that uses an array to store its entries in ascending order. The insertion point can be used to insert the new entry into the queue accordingly.

    Binary search an array or list

    Wrapping Up

    Java’s standard binary search methods on java.util.Arrays and java.util.Collections allow you to find an item or locate the insertion point for a new item within an array or list. Binary search works only on sorted arrays or lists. It has logarithmic run time, making it very efficient for big data structures: Given a sorted array of size 100,000, the maximum required steps for binary search to find an item are log(100,000) / log(2) ≈ 17. On small data structures, the added overhead can make binary search slower than a linear scan.

    Frequently Asked Questions (FAQs) about Java’s Binary Search API

    What is the purpose of Java’s Binary Search API?

    Java’s Binary Search API is a powerful tool used for searching elements in an array or list. It uses the binary search algorithm, which is a divide and conquer strategy. This algorithm works by dividing the array into two halves and then searching the required element in one of the halves. This process continues until the element is found or the subarray size becomes zero. The Binary Search API is efficient and fast, making it ideal for handling large data sets.

    How does the Binary Search API differ from other search methods in Java?

    The Binary Search API differs from other search methods in Java primarily in terms of efficiency. While linear search methods scan each element of an array one by one, the Binary Search API divides the array into halves, significantly reducing the number of comparisons needed to find an element. However, it’s important to note that the Binary Search API requires the array to be sorted before it can be used.

    Can I use the Binary Search API with unsorted arrays?

    No, the Binary Search API cannot be used with unsorted arrays. The binary search algorithm works on the principle of dividing the array into two halves, which requires the array to be sorted. If the array is not sorted, the results of the binary search will be unpredictable.

    How can I sort an array before using the Binary Search API?

    Java provides several methods to sort an array. The simplest way is to use the Arrays.sort() method. This method sorts the specified array into ascending numerical order.

    What happens if the element is not found in the array using Binary Search API?

    If the element is not found in the array, the Binary Search API will return a negative value. This value is the “insertion point” which is the point at which the key would be inserted into the array.

    Can I use the Binary Search API with arrays of objects?

    Yes, you can use the Binary Search API with arrays of objects. However, the objects must implement the Comparable interface, and the array must be sorted according to the natural ordering of its elements.

    What is the time complexity of the Binary Search API?

    The time complexity of the Binary Search API is O(log n), where n is the number of elements in the array. This makes it a very efficient search method for large data sets.

    Can I use the Binary Search API with lists?

    Yes, you can use the Binary Search API with lists. The Collections class provides a binarySearch() method that works with lists. However, similar to arrays, the list must be sorted before you can use the binary search.

    How does the Binary Search API handle duplicate elements in the array?

    If there are duplicate elements in the array, the Binary Search API does not guarantee which one will be found. It will return the index of any of the duplicate elements.

    Can I use the Binary Search API with arrays of primitive types?

    Yes, you can use the Binary Search API with arrays of primitive types. The Arrays class provides overloaded binarySearch() methods for different primitive types like int, long, double, etc.