Java Collections binarySearch()

In this guide, you will learn about the Collections binarySearch() method in Java programming and how to use it with an example.

1. Collections binarySearch() Method Overview

Definition:

The binarySearch() method from the Collections class in Java is used to search for an element in a sorted list using the binary search algorithm.

Syntax:

Collections.binarySearch(List<? extends Comparable<? super T>> list, T key)

Parameters:

- list: The list to be searched.

- key: The key to be searched for.

Key Points:

- The list must be sorted in ascending order according to the natural ordering of its elements (or by the comparator provided) for the binary search algorithm to work correctly.

- If the list contains multiple elements equal to the specified key, there's no guarantee which one will be found.

- If the list is not sorted or contains elements that are not mutually comparable, the results are undefined.

- There are overloaded versions of binarySearch() that take a custom comparator for determining order.

- Returns the index of the search key, if it is contained in the list; otherwise, it returns (-(insertion point) - 1). The insertion point is the point at which the key would be inserted into the list.

2. Collections binarySearch() Method Example

import java.util.*;

public class CollectionsBinarySearchExample {
    public static void main(String[] args) {
        List<Integer> numbers = new ArrayList<>(Arrays.asList(1, 3, 5, 7, 9));

        // Searching for the number 5
        int index = Collections.binarySearch(numbers, 5);
        System.out.println("Index of 5: " + index);

        // Searching for a number that doesn't exist
        int notFound = Collections.binarySearch(numbers, 6);
        System.out.println("Index of 6: " + notFound);

        // Searching with custom comparator
        List<String> words = new ArrayList<>(Arrays.asList("apple", "banana", "kiwi"));
        int wordIndex = Collections.binarySearch(words, "kiwi", Comparator.comparingInt(String::length));
        System.out.println("Index of 'kiwi' based on length: " + wordIndex);
    }
}

Output:

Index of 5: 2
Index of 6: -4
Index of 'kiwi' based on length: 2

Explanation:

In the example, we first create a sorted list of integers and search for the number 5 using the binarySearch() method, which returns its index. 

We then attempt to search for a number that doesn't exist in the list, which returns a negative index indicating where the number would be inserted to maintain the sorted order. 

Lastly, we search for a word using a custom comparator based on string length. The results showcase the functionality of the binarySearch() method and its variations.