Arrays binarySearch() Method in Java

Introduction

The Arrays.binarySearch() method in Java is used to search for a specified element within a sorted array using the binary search algorithm. This method is part of the java.util package and is highly efficient for searching elements in large arrays due to its logarithmic time complexity – O(logn).

The Arrays.binarySearch() method is overloaded, allowing it to work with different data types and scenarios, including searching subranges and using custom comparators for object arrays.

Key Points:

• Efficiency: The method is efficient, with a time complexity of O(logn) for searching sorted arrays.
• Overloaded Methods: Supports various data types, including int, double, char, Object, and more.
• Custom Comparators: Allows custom sorting and searching for complex data types using comparators.
• Return Value: Returns the index of the element if found; otherwise, returns a negative value indicating the insertion point.

Syntax

The Arrays.binarySearch() method has several overloaded versions. Here are some of the common signatures:

int index = Arrays.binarySearch(array, key);
int index = Arrays.binarySearch(array, fromIndex, toIndex, key);
int index = Arrays.binarySearch(array, key, comparator);
int index = Arrays.binarySearch(array, fromIndex, toIndex, key, comparator);

• array: The sorted array to search.
• key: The value to search for in the array.
• fromIndex: The starting index of the subrange to search (inclusive).
• toIndex: The ending index of the subrange to search (exclusive).
• comparator: The comparator used to define the ordering of the array for custom object types.

Example: Using Arrays.binarySearch()

Let’s explore how to use the Arrays.binarySearch() method with various examples.

Example 1: Searching in an Array of Integers

import java.util.Arrays;

public class BinarySearchExample {
    public static void main(String[] args) {
        // Sorted array of integers
        int[] numbers = {1, 3, 5, 7, 9, 11};

        // Search for a key in the array
        int key = 7;
        int index = Arrays.binarySearch(numbers, key);

        // Print the index of the key
        System.out.println("Index of " + key + ": " + index);

        // Search for a key not in the array
        key = 4;
        index = Arrays.binarySearch(numbers, key);

        // Print the negative insertion point
        System.out.println("Index of " + key + ": " + index);
    }
}

Output:

Index of 7: 3
Index of 4: -3

Explanation:

• Found Key: The method returns the index of the key if it is found in the array.
• Not Found: The method returns a negative value indicating the insertion point if the key is not found. The insertion point is (-(index + 1)).

Example 2: Searching in a Subrange of an Array

import java.util.Arrays;

public class SubrangeBinarySearch {
    public static void main(String[] args) {
        // Sorted array of integers
        int[] numbers = {1, 3, 5, 7, 9, 11, 13, 15};

        // Search for a key within a subrange
        int key = 11;
        int fromIndex = 3;
        int toIndex = 7;
        int index = Arrays.binarySearch(numbers, fromIndex, toIndex, key);

        // Print the index of the key
        System.out.println("Index of " + key + " in subrange: " + index);

        // Search for a key not in the subrange
        key = 1;
        index = Arrays.binarySearch(numbers, fromIndex, toIndex, key);

        // Print the negative insertion point
        System.out.println("Index of " + key + " in subrange: " + index);
    }
}

Output:

Index of 11 in subrange: 5
Index of 1 in subrange: -4

Explanation:

• Subrange Search: The method searches only within the specified subrange.
• Insertion Point: If the key is not found in the subrange, it returns the negative insertion point for that subrange.

Example 3: Searching in an Array of Objects with a Comparator

import java.util.Arrays;
import java.util.Comparator;

class Person {
    String name;
    int age;

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

    @Override
    public String toString() {
        return name + " (" + age + ")";
    }
}

public class ObjectBinarySearch {
    public static void main(String[] args) {
        // Sorted array of Person objects by age
        Person[] people = {
            new Person("Alice", 30),
            new Person("Bob", 25),
            new Person("Charlie", 35)
        };

        // Sort the array using a comparator
        Arrays.sort(people, Comparator.comparingInt(p -> p.age));

        // Search for a person by age
        Person key = new Person("Unknown", 25);
        int index = Arrays.binarySearch(people, key, Comparator.comparingInt(p -> p.age));

        // Print the index and the found person
        System.out.println("Index of " + key.age + ": " + index);
        System.out.println("Found: " + people[index]);
    }
}

Output:

Index of 25: 0
Found: Bob (25)

Explanation:

• Custom Comparator: The method uses a custom comparator to define the ordering of the array.
• Complex Types: This approach allows binary search on complex objects with specific fields.

Real-World Use Case

In real-world applications, Arrays.binarySearch() is useful for searching in sorted datasets, such as finding records in a sorted database or searching for values in sorted collections.

Example: Searching in a Sorted Log File

Consider a scenario where you need to search for specific log entries in a sorted log file by timestamp.

import java.util.Arrays;
import java.util.Comparator;

class LogEntry {
    String timestamp;
    String message;

    LogEntry(String timestamp, String message) {
        this.timestamp = timestamp;
        this.message = message;
    }

    @Override
    public String toString() {
        return timestamp + ": " + message;
    }
}

public class LogSearch {
    public static void main(String[] args) {
        // Sorted array of log entries by timestamp
        LogEntry[] logs = {
            new LogEntry("2024-08-01 10:00:00", "System started"),
            new LogEntry("2024-08-01 10:05:00", "User logged in"),
            new LogEntry("2024-08-01 10:10:00", "Error: Disk full")
        };

        // Sort the array using a comparator
        Arrays.sort(logs, Comparator.comparing(log -> log.timestamp));

        // Search for a log entry by timestamp
        LogEntry key = new LogEntry("2024-08-01 10:05:00", null);
        int index = Arrays.binarySearch(logs, key, Comparator.comparing(log -> log.timestamp));

        // Print the index and the found log entry
        System.out.println("Index of log entry: " + index);
        System.out.println("Found Log Entry: " + logs[index]);
    }
}

Output:

Index of log entry: 1
Found Log Entry: 2024-08-01 10:05:00: User logged in

Explanation:

• Sorted Log Entries: Log entries are sorted by timestamp, allowing for efficient searching.
• Comparator: A comparator is used to define the ordering of log entries by timestamp.

Conclusion

The Arrays.binarySearch() method in Java provides an efficient way to search for elements in sorted arrays. With its overloaded methods, it supports various data types and custom comparators, making it versatile for different scenarios.

Summary:

• Efficiency: Offers efficient search with logarithmic time complexity.
• Overloaded Methods: Supports multiple data types and custom comparators.
• Use Cases: Suitable for searching in sorted datasets, such as log files and databases.
• Return Value: Returns the index of the element if found, or a negative insertion point if not found.

By leveraging the Arrays.binarySearch() method, developers can perform efficient searches in sorted collections, ensuring optimal performance and flexibility in their applications.