Java uses the binarySearch() function of the Collections class to perform a binary search in an ordered collection.

Java uses the binarySearch() function of the Collections class to perform binary search in ordered collections

Binary search is an efficient algorithm for finding specific elements in ordered collections. In Java, we can use the binarySearch() function of the Collections class to implement binary search. This article will introduce how to use the binarySearch() function to search in an ordered collection and provide specific code examples.

The basic idea of ​​the binary search algorithm is to compare the element to be searched with the middle element of the ordered set. If the middle element is equal to the element to be searched, the search is successful; if the middle element is greater than the element to be searched, then the The search continues in the left half of the set; if the middle element is smaller than the element to be found, the search continues in the right half of the set. By continuously narrowing the search scope, the target element can eventually be found or determined not to exist in the collection.

In Java, we can use the binarySearch() function of the Collections class to implement binary search. The definition of this function is as follows:

public static int binarySearch(List extends Comparable super T>> list, T key)

This function accepts an array that implements the Comparable interface It takes a sorted set and the element to be found as parameters and returns the index value of the element in the set. If the element does not exist in the collection, a negative number is returned that is the negative value of the position where the element should be inserted minus one (i.e. - (insert position 1)).

The following is a code example for binary search using the binarySearch() function of the Collections class:

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

public class BinarySearchExample {

public static void main(String[] args) {
    List<Integer> list = new ArrayList<>();
    list.add(1);
    list.add(3);
    list.add(5);
    list.add(7);
    list.add(9);

    int index = Collections.binarySearch(list, 5);
    if (index >= 0) {
        System.out.println("Element found at index " + index);
    } else {
        System.out.println("Element not found. Insertion point: " + (-(index + 1)));
    }
}

}

In the above code, we create an integer ArrayList, which contains some sequence of integers. We called the binarySearch() function of the Collections class to find the index value of element 5 in the collection. Since the element exists in the collection, the index value of the element is returned. Eventually we will print out "Element found at index 2".

If we look for an element in the collection that does not exist, say 4, we will get a negative number indicating the position where the element should be inserted. In the above code, since 4 should be inserted at index 1, the negative number returned is -(1 1) = -2. After executing the code we will see the output of "Element not found. Insertion point: -2".

By using the binarySearch() function of the Collections class, we can easily perform a binary search in an ordered collection. The time complexity of this algorithm is O(logN), so binary search has high efficiency and advantages when processing large-scale data.

Summary:
This article introduces the method of using the binarySearch() function of the Collections class to perform binary search in an ordered collection in Java. By using this function, we can quickly find the position of a specific element in the collection. I hope that through the introduction and code examples of this article, readers can master the application and usage of the binary search algorithm and improve their efficiency and skills in programming.

The above is the detailed content of Java uses the binarySearch() function of the Collections class to perform a binary search in an ordered collection.. For more information, please follow other related articles on the PHP Chinese website!