Searching Arrays

The Arrays.binarySearch() method is a powerful tool for quickly finding elements in sorted arrays. This method is part of the java.util.Arrays utility class and uses binary search, which has a time complexity of O(log⁡ n). However, binarySearch() only works correctly on arrays that are already sorted in ascending order.

Basic Usage of Arrays.binarySearch()

The binarySearch() method takes two main parameters: the array and the target value to search for. If the target element is found, it returns the index of the element; otherwise, it returns a negative value indicating where the element would be inserted to maintain order.

Example:

int[] numbers = {1, 3, 5, 7, 9};
int index = Arrays.binarySearch(numbers, 5); // Searches for 5
System.out.println(index); // Output: 2 (index of element 5)

What If the Element Is Not Found?

If the target element does not exist in the array, binarySearch() returns a negative value. Specifically, it returns -(insertion_point + 1), where insertion_point is the index where the element would be inserted to keep the array sorted.

Example (Element Not Found):

int[] numbers = {1, 3, 5, 7, 9};
int index = Arrays.binarySearch(numbers, 4); // Searches for 4
System.out.println(index); // Output: -3

In this case, -3 indicates that 4 is not found and would be inserted at index 2 (if you remove the negative sign and subtract 1).

Important Notes

1. Array Must Be Sorted: binarySearch() only works correctly on sorted arrays. If the array is not sorted, the results are unpredictable.
2. Works with Primitives and Objects: binarySearch() has overloaded methods that work with primitive arrays (e.g., int[], double[]) and object arrays (e.g., String[]), as long as the array is sorted in ascending order.
3. Using Comparators with Object Arrays: When searching in custom object arrays, you can use the overloaded method that takes a Comparator. This is useful for complex sorting orders or objects that do not implement Comparable.

Example with Custom Objects:

class Person {
    String name;
    int age;

    Person(String name, int age) {
        this.name = name;
        this.age = age;
    }
}

Person[] people = {
    new Person("Alice", 30),
    new Person("Bob", 25),
    new Person("Charlie", 20)
};

// Sort by age, then use binarySearch with a Comparator
Arrays.sort(people, Comparator.comparingInt(p -> p.age));
int index = Arrays.binarySearch(people, new Person("", 25), Comparator.comparingInt(p -> p.age));
System.out.println(index); // Output: 1 (index of "Bob" who is 25)

Summary

Arrays.binarySearch() is an efficient method for finding elements in sorted arrays, with quick lookups thanks to binary search. It’s important to remember that the array must be sorted, and it works well with both primitive and object arrays, supporting custom Comparator logic for objects.