Collections Binary Search in Java

1. Basic Algorithm of Binary Search
2. Syntax of Collections.binarySearch() in Java
3. Types of Searches Using Collections.binarySearch() in Java
4. Conclusion

The Java Collections class has an internal method called binarySearch() that returns the object’s position in a sorted list. The parameter of the Collections binarySearch() function allows for differentiation depending on the different parameters of the script.

The binary search algorithm is used by Collections.binarySearch() to search the supplied list for the requested object. BeforeBefore making this call, the list must be sorted in ascending order using the natural ordering of its items.

If it is not sorted, the outcomes are not clear. There is no certainty that the desired element will be located if the list contains many elements identical to the requested object.

Basic Algorithm of Binary Search

In the binary search, the collection is repeatedly split in half. Depending on whether the key element is less than or greater than the collection’s middle element, the collection’s left or right half is searched for the key element.

Steps to follow in a binary search algorithm:

1. Determine the collection’s midpoint.
2. Compare the mid-element to the essential components.
3. You return the mid-index position for the key discovered if the key is the same as the middle element.
4. Else, if the key > mid element, the key is in the collection’s right half. Repeat steps 1 through 3 to complete the collection’s lower (right) half.
5. If the key is a mid-element, then the key is in the collection’s upper half. As a result, you must do the binary search again in the upper half.

Syntax of Collections.binarySearch() in Java

The following syntax is used to declare this method.

public static <T> int binarySearch(List<? extends Comparable<? super T>> list,
    T key) public static <T> int binarySearch(List<? extends T> list, T key,
    Comparator<? super T> c)

There are 2 types of Collections.binarySearch() methods:

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

   Before using the procedure, the list must be arranged in ascending order using the provided natural number. The results are undefinable if the list is not sorted.

2. Java Collections binarySearch(List<? extends T> list, T key, Comparator<? super T> c).

   Before calling the procedure, the list must be arranged in ascending order using the supplied comparator.

Types of Searches Using Collections.binarySearch() in Java

For the binarySearch() to function as intended, your data must be ordered by the provided comparator. Before making this call, the list must be sorted in ascending order using the supplied comparator.

The procedure will provide the index of the sought-after element if the data is sorted; otherwise, it will return (-(insertion point) - 1).

Search an integer key in an ascending ordered list.

Example Code:

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Main {
  public static void main(String[] args) {
    List<Integer> al = new ArrayList<Integer>();
    al.add(3);
    al.add(4);
    al.add(5);
    al.add(20);
    al.add(30);

    int index = Collections.binarySearch(al, 20);
    System.out.println(index);

    index = Collections.binarySearch(al, 12);
    System.out.println(index);
  }
}

Output:

3
-4

Search an integer key in a descending ordered list.

Example Code:

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Main {
  public static void main(String[] args) {
    List<Integer> al = new ArrayList<Integer>();
    al.add(350);
    al.add(90);
    al.add(45);
    al.add(20);
    al.add(3);

    int index = Collections.binarySearch(al, 45, Collections.reverseOrder());

    System.out.println(index);
  }
}

Output:

2

Conclusion

The Collections binarySearch() is the most popular search method. Here, the condition is that the data must be sorted in ascending order for a binary search to be successful.

Iterative or recursive methods can both be used to implement a binary search. The Java Arrays class additionally offers the binarySearch() method, which conducts a binary search on an array.