binarySearch() – search array

Arrays.binarySearch() is a static method in Java’s java.util.Arrays class that performs a binary search on a sorted array to find the index of a specified value. Binary search is an efficient algorithm with a time complexity of O(log n), making it suitable for large datasets. However, it requires the array to be sorted beforehand.

Key Points of Arrays.binarySearch()

1. Binary Search Algorithm:
   • The method uses a binary search algorithm, which repeatedly divides the search interval in half.
   • If the value of the search key is less than the item in the middle of the interval, the search continues in the lower half; otherwise, it continues in the upper half.
   • This process repeats until the value is found or the interval is empty.
2. Array Must Be Sorted:
   • For Arrays.binarySearch() to work correctly, the array must be sorted in ascending order.
   • If the array is not sorted, the result is undefined.
3. Return Values:
   • If the key is found, the method returns the index of the key.
   • If the key is not found, the method returns -(insertion point) - 1, where the insertion point is the index at which the key would be inserted to maintain the sorted order.
4. Overloaded Methods:
   • Arrays.binarySearch() is overloaded to handle different types of arrays, including primitive types (e.g., int, char, double) and object types.
   • It also allows for custom comparators when searching in arrays of objects.

Overloaded Methods

Here are the main overloaded variants of the Arrays.binarySearch() method:

• public static int binarySearch(byte[] a, byte key)
• public static int binarySearch(char[] a, char key)
• public static int binarySearch(double[] a, double key)
• public static int binarySearch(float[] a, float key)
• public static int binarySearch(int[] a, int key)
• public static int binarySearch(long[] a, long key)
• public static int binarySearch(short[] a, short key)
• public static int binarySearch(Object[] a, Object key)
• public static <T> int binarySearch(T[] a, T key, Comparator<? super T> c)

Examples

Binary Search in Primitive Type Arrays

import java.util.Arrays;

public class BinarySearchExample {
    public static void main(String[] args) {
        int[] intArray = {1, 3, 5, 7, 9, 11, 13};

        // Performing binary search for value 7
        int index = Arrays.binarySearch(intArray, 7);
        System.out.println("Index of 7: " + index); // Output: Index of 7: 3

        // Performing binary search for value 2 (not in array)
        index = Arrays.binarySearch(intArray, 2);
        System.out.println("Index of 2: " + index); // Output: Index of 2: -2
    }
}

Binary Search in Object Type Arrays

import java.util.Arrays;

public class BinarySearchExample {
    public static void main(String[] args) {
        String[] stringArray = {"apple", "banana", "cherry", "date", "fig", "grape"};

        // Performing binary search for value "date"
        int index = Arrays.binarySearch(stringArray, "date");
        System.out.println("Index of date: " + index); // Output: Index of date: 3

        // Performing binary search for value "coconut" (not in array)
        index = Arrays.binarySearch(stringArray, "coconut");
        System.out.println("Index of coconut: " + index); // Output: Index of coconut: -3
    }
}

Binary Search with Custom Comparator

For object arrays, you can define a custom order by using a Comparator.

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

public class BinarySearchExample {
    public static void main(String[] args) {
        String[] stringArray = {"apple", "banana", "cherry", "date", "fig", "grape"};

        // Sorting array in reverse order
        Arrays.sort(stringArray, Comparator.reverseOrder());

        // Performing binary search for value "date" with custom comparator
        int index = Arrays.binarySearch(stringArray, "date", Comparator.reverseOrder());
        System.out.println("Index of date: " + index); // Output: Index of date: 2

        // Performing binary search for value "coconut" (not in array) with custom comparator
        index = Arrays.binarySearch(stringArray, "coconut", Comparator.reverseOrder());
        System.out.println("Index of coconut: " + index); // Output: Index of coconut: -4
    }
}

Important Considerations

• Array Must Be Sorted: Ensure the array is sorted before performing a binary search. Use Arrays.sort() if needed.
• Performance: Binary search is efficient with a time complexity of O(log n), but it is only applicable to sorted arrays.
• Insertion Point: When the key is not found, the negative insertion point value can be useful to determine where the key should be inserted to maintain sorted order.

Practical Applications

• Searching in Large Datasets: Binary search is ideal for quickly finding elements in large sorted datasets.
• Efficient Insertions: By using the negative insertion point value, you can efficiently insert elements while maintaining the sorted order of an array.

In summary, Arrays.binarySearch() is a powerful method for searching elements in sorted arrays in Java. It offers efficient search capabilities with support for custom comparators, making it versatile for various data types and sorting orders.